题目描述

给定一个 n 个点 m 条边的边带权简单连通无向图，在 0 时刻你在点 1 上。

假设当前是 t 时刻，你在点 v 上，你可以选择两种操作：

1. 仍停留在点 v 上，操作后到 t+1 时刻。
2. 选择一条边 (a,b,w) 满足 a=v 或 b=v，则你到这条边连接的另一个点上，操作后到 t+w 时刻。

有 k 条信息，每一条信息形如 $(t_i,v_i)$表示在 $t_i$时刻，点 $v_i$上会出现一只飞猪，其编号为 i，若该时刻你在 $v_i$上，则你捕获到了 i 号飞猪。

现在你需要求出你能捕获到的飞猪数量的最大值。

输入格式

第一行为三个正整数 n,m,k。

接下来 m 行每行三个正整数 $a_i,b_i,w_i$。

接下来 k 行每行两个正整数 $t_i,v_i$。

输出格式

一行一个整数，为你能捕获到的飞猪数量的最大值。

数据范围

$2≤n≤200$
$1≤k≤5000$

样例

Input:
2 1 5
1 2 2
1 2
2 2
3 2
5 1
7 2

Output:
4

算法1(考场假算法)

(贪心) $O(n^3+klogk)$

说明：如果您非常希望看到AC题解，请跳过。

这是比赛时本人灵机一动想到的假算法。
这个题目我考场上先想到了暴搜，抱灵了，但是在搞完T4和T5的77分后想到了这个算法：把飞猪按照出现时间排序并维护一下上一次走到的点last。扫描飞猪序列，如果last与当前飞猪的落脚点距离不到出现间隔时间t，就抓住这只飞猪。
但是这种是个人就能Hack掉的代码居然AC了！
对于距离，用Floyd搞一遍就行了

C++ 代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <ctime>
#include <cstdlib>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#define pii pair<int, int>
#define maxn 210
#define maxm 5010
#define x first
#define y second

using namespace std;

int n, m, K;
int d[maxn][maxn];
pii pig[maxm];

int main()
{
    scanf("%d%d%d", &n, &m, &K);
    memset(d, 0x3f, sizeof d);
    for (int i = 1; i <= m; i ++ )
    {
        int a, b, w;
        scanf("%d%d%d", &a, &b, &w);
        d[a][b] = d[b][a] = w;
    }
    for (int i = 1; i <= K; i ++ ) scanf("%d%d", &pig[i].x, &pig[i].y);
    sort(pig + 1, pig + K + 1);

    for (int i = 1; i <= n; i ++ ) d[i][i] = 0;
    for (int k = 1; k <= n; k ++ )
        for (int i = 1; i <= n; i ++ )
            for (int j = 1; j <= n; j ++ )
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);

    int lst = 1, t = 0, ans = 0;
    for (int i = 1; i <= K; i ++ )
    {
        int u = pig[i].y;
        if (d[lst][u] <= pig[i].x - t)
        {
            ans ++ ;
            lst = u;
            t = pig[i].x;
        }
    }

    cout << ans << endl;

    return 0;
}

算法2(正解)

(Dp) $O(n^3+k^2)$

说明：如果您已经看完了算法1，请把上面的内容全部忘掉，算法1只是想告诉大家，有时候假贪心是不会被数据卡掉的。

下面是本题的正解。
将所有飞猪按照出现时间排序。我们不妨假设，第0只飞猪在1号节点出现。
令$f_i$表示已经扫描完前$i$只飞猪所能抓到的飞猪的最大数量。
状态转移比较显然，如果两个出现过飞猪的节点之间的距离小于时间间隔，两个节点的状态就可以相互转移。
距离依旧Floyd，所以为$O(n^3+k^2)$的复杂度。

C++ 代码

#include <bits/stdc++.h>
#define maxn 210
#define maxk 5010

using namespace std;

int n, m, K;
int d[maxn][maxn];
struct Event{
    int t, v;
    bool operator<(const Event &W)const {
        return t < W.t;
    }
}event[maxk];
int f[maxk];

int main()
{
    scanf("%d%d%d", &n, &m, &K);
    memset(d, 0x3f, sizeof d);
    for (int i = 1; i <= n; i ++ ) d[i][i] = 0;

    for (int i = 1; i <= m; i ++ )
    {
        int a, b, w;
        scanf("%d%d%d", &a, &b, &w);
        d[a][b] = d[b][a] = w;
    }
    for (int i = 1; i <= K; i ++ ) scanf("%d%d", &event[i].t, &event[i].v);
    sort(event + 1, event + K + 1);
    event[0] = {0, 1};

    for (int k = 1; k <= n; k ++ )
        for (int i = 1; i <= n; i ++ )
            for (int j = 1; j <= n; j ++ )
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);

    for (int i = 1; i <= K; i ++ )
        for (int j = 0; j < i; j ++ )
        {
            int vi = event[i].v, vj = event[j].v;
            if (d[vj][vi] <= event[i].t - event[j].t)
                f[i] = max(f[i], f[j] + 1);
        }

    printf("%d\n", f[K]);

    return 0;
}