题意：
给定一个点数为 n，边数为 m，权值不超过 \(10^9\) 的带权连通图，没有自环与重边。 现在要求对于每一条边求出，这条边的边权最大为多少时，它还能出现在所有可能的最小生成树上，如果对于任意边权都出现，则输出 \(-1\)。
这里写一个用倍增的\(O(nlogn)\)做法。
先求出一个最小生成树。
1、若x到y在树上，那么对于任意一条非树边\(e(a,b)\)，若满足a到b的树上路径经过\(e(x,y)\)， 那么，根据最小生成树的性质，添加\(e(a,b)\)后生成的环上的最大边必须是唯一的\(e(a,b)\)。 因此，\(e(x,y)\)的权值应当等于所有满足条件的\(e(a,b)\)的最小权值减1。
2、若x到y不在树上，那么，根据最小生成树的性质，添加\(e(x,y)\)后生成的环上的最大边如果不是\(e(x,y)\)，它就能出现。 因此，\(e(x,y)\)的权值应当等于x到y路径上的最大值减1。
2可以使用倍增，\(O(nlogn)\)。
对于1，我们可以把非树边从小到大排序，再依次做链上覆盖，保证每条树边只被其第一次覆盖。 可以把被覆盖的连续边存成一个集合，用并查集维护。
具体来说，并查集的根节点代表此点向上第一个未被覆盖的点（包括自身）。 在这个点被覆盖后，把它与它的父节点的集合合并。
每个点只会被考虑一次，所以复杂度是对的。 总时间复杂度：\(O(nlogn)\)，很好写。
代码：
#include <stdio.h> #include <stdlib.h> struct SBi { int x, y, z; SBi() {} SBi(int X, int Y, int Z) { x = X; y = Y; z = Z; } }; SBi bi[200010],px[200010]; int cmp(const void * a, const void * b) { return ((SBi * ) a) ->z - ((SBi * ) b) ->z; } int fu[200010],fr[200010],ne[400010],v[400010],w[400010],bs = 0; int getv(int x) { if (fu[x] == x) return x; fu[x] = getv(fu[x]); return fu[x]; } void addb(int a, int b, int c) { v[bs] = b; w[bs] = c; ne[bs] = fr[a]; fr[a] = bs++; } void kru(int n, int m) { for (int i = 1; i <= n; i++) { fu[i] = i; fr[i] = -1; } qsort(bi, m, sizeof(SBi), cmp); for (int i = 0; i < m; i++) { int x = getv(bi[i].x),y = getv(bi[i].y); if (x == y) continue; fu[x] = y; addb(bi[i].x, bi[i].y, bi[i].z); addb(bi[i].y, bi[i].x, bi[i].z); } } int fa[200010],sd[200010],fb[200010],fg[200010]; void dfs1(int u, int f) { fa[u] = f;sd[u] = sd[f] + 1; for (int i = fr[u]; i != -1; i = ne[i]) { if (v[i] != f) { fb[v[i]] = w[i]; dfs1(v[i], u); } } } int x[200010],y[200010],z[200010],bz[18][200010],zd[18][200010]; void yucl(int n) { for (int i = 1; i <= n; i++) { bz[0][i] = fa[i]; zd[0][i] = fb[i]; } for (int i = 1; i <= 17; i++) { for (int x = 1; x <= n; x++) { bz[i][x] = bz[i - 1][bz[i - 1][x]]; zd[i][x] = zd[i - 1][bz[i - 1][x]]; if (zd[i - 1][x] > zd[i][x]) zd[i][x] = zd[i - 1][x]; } } } int getlca(int a, int b) { if (sd[a] < sd[b]) { int t = a; a = b;b = t; } for (int i = 17; i >= 0; i--) { if (sd[bz[i][a]] >= sd[b]) a = bz[i][a]; } if (a == b) return a; int rt; for (int i = 17; i >= 0; i--) { if (bz[i][a] == bz[i][b]) rt = bz[i][a]; else { a = bz[i][a]; b = bz[i][b]; } } return rt; } int getmax(int a, int b) { int lc = getlca(a, b),ma = -1; for (int i = 17; i >= 0; i--) { if (sd[bz[i][a]] >= sd[lc]) { if (zd[i][a] > ma) ma = zd[i][a]; a = bz[i][a]; } } for (int i = 17; i >= 0; i--) { if (sd[bz[i][b]] >= sd[lc]) { if (zd[i][b] > ma) ma = zd[i][b]; b = bz[i][b]; } } return ma; } void fugai(int a, int b, int c) { while (sd[a = getv(a)] > sd[b]) { fg[a] = c; fu[a] = getv(fa[a]); } } int main() { int n,m,k = 0; scanf("%d%d", &n, &m); for (int i = 0; i < m; i++) { scanf("%d%d%d", &x[i], &y[i], &z[i]); bi[i] = SBi(x[i], y[i], z[i]); } kru(n, m);dfs1(1, 0);yucl(n); for (int i = 1; i <= n; i++) fu[i] = i; for (int i = 0; i < m; i++) { int a = x[i],b = y[i]; if (fa[a] != b && fa[b] != a) bi[k++] = SBi(a, b, z[i]); } qsort(bi, k, sizeof(SBi), cmp); for (int i = 0; i < k; i++) { int a = bi[i].x,b = bi[i].y,c = bi[i].z; int lc = getlca(a, b); fugai(a, lc, c);fugai(b, lc, c); } for (int i = 0; i < m; i++) { int a = x[i],b = y[i]; if (fa[b] == a) { a = y[i]; b = x[i]; } if (fa[a] != b) printf("%d ", getmax(a, b) - 1); else printf("%d ", fg[a] - 1); } return 0; }