Codeforces 1081D(最小瓶颈路+边贡献思想)

发表于 | 分类于 | | + s

Codeforces 1081D
题意：给定$n$点$m$边无向连通图，一条路径长度定义为其边的最大值，两个点之间的距离为他们之间最短路径长度。现在给$k$个特殊点，请对每个特殊点找到另一个最远的特殊点，输出距离。
根据距离的定义，求出原图的最小生成树(最小瓶颈生成树)，树上两点的唯一路径就是两点距离。并且所有两两点之间的距离最大值是某一条边的边权。
那么我们根据边权从小到大枚举每条树上的边来判断是否能成为这条边。这条边应该在$k$个点组成的虚树上。但是并不用那么麻烦，对于每条边判断他左边是否有特殊点，右边是否有特殊点，都有这条边才有可能成为这条边，否则不可能有任意一条路径经过该边。
根据连通图和相关性质观察发现，最后答案都是一样的。

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<map>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;

namespace flyinthesky {

    const int MAXN = 100000 + 5;

    struct edge {
        int u, v, w;
        bool operator < (const edge &rhs) const {return w < rhs.w;}
    }ed[MAXN];

    int n, m, k, sz[MAXN], f[MAXN];

    int find(int x) {return f[x] == x ? x : f[x] = find(f[x]);}

    void clean() {
    }
    int solve() {
        clean();
        cin >> n >> m >> k;
        for (int i = 1; i <= n; ++i) f[i] = i;
        for (int x, i = 1; i <= k; ++i) scanf("%d", &x), sz[x] = 1;
        for (int i = 1; i <= m; ++i) scanf("%d%d%d", &ed[i].u, &ed[i].v, &ed[i].w);
        sort(ed + 1, ed + 1 + m);
        int ans = 0;
        for (int i = 1; i <= m; ++i) {
            int x = find(ed[i].u), y = find(ed[i].v);
            if (x != y) {
                if (sz[x] && sz[y]) ans = max(ans, ed[i].w);
                f[y] = x, sz[x] += sz[y];
            }
        } 
        for (int i = 1; i <= k; ++i) printf("%d ", ans);
        return 0;
    }
}
int main() {
    flyinthesky::solve();
    return 0;
}
------ 本文结束 ------