题解 P6111 【[USACO18JAN]MooTube S】

tribool4_in · 2021-03-20 18:16:07 · 题解

似乎有很多题解用的是 离线+并查集，然而蒟蒻表示根本看不懂做法……

于是乎我打了个暴力 DFS，然后交了一通，结果就过了？？？

思路很简单，首先题目说，如果一个点 u 的推荐视频中包含 v，必须要保证两点之间的路径的最小边长 \ge k。

显然，如果两点之间的路径的最小边长都 \ge k，则每条边长肯定都必须 \ge k。

因此，对于每个询问，从当前点出发进行深搜，如果当前边的长度 < k，则说明无法走通，否则情况数加一并继续深搜。

代码：

#include <bits/stdc++.h>
using namespace std;
const int N = 5e3 + 5;
int n, q, cnt = 0;
vector<int> G[N];
int g[N][N]; // 其实存图可以不用邻接矩阵，不过反正空间足够，存了也没事
void dfs(int u, int fa, int k) {
    for (int i = 0; i < G[u].size(); i++) {
        int v = G[u][i]; int w = g[u][v];
        if (v != fa && w >= k) {
            cnt++;
            dfs(v, u, k);
        }
    }
}
int main() {
    scanf("%d%d", &n, &q);
    for (int i = 1; i < n; i++) {
        int p, q, r;
        scanf("%d%d%d", &p, &q, &r);
        G[p].push_back(q), G[q].push_back(p), g[p][q] = g[q][p] = r;
    }
    for (int i = 1; i <= q; i++) {
        int k, v;
        scanf("%d%d", &k, &v);
        cnt = 0;
        dfs(v, -1, k);
        printf("%d\n", cnt);
    }
    return 0;
}