c/c++语言开发共享cf160D. Edges in MST(最小生成树 桥)

题意

题目链接

给出一棵树，确定每条边状态: 一定在mst上 / 可能在mst上 / 不可能在mst上

(n leqslant 10^5, m leqslant 10^5)

sol

mst表示最小生成树

表示只能想到(nlog^2n)的做法：先求出mst。然后枚举剩下的边，如果权值出现在形成的环上，那么该边和mst上的边都是可能出现，如果权值大于环上最大值，那么该边不可能在mst上。没有被标记过的边一定在mst上。

树剖+主席树维护一下。。

标算好神仙啊。

结论：将任意两个mst上的边排序后，得到的序列是相同的

自己xjbyy的证明：

反证法。

若不满足条件，则两个序列中一定存在四个位置

(x_1, y_1)

(x_2, y_2)

满足(x_1 < x_2)且(y_1 > y_2)。(如果只有一个不同的话权值大的不会成为mst)

那么把(x_1)加入到第二个mst中，同时删去环上最大的边，会得到一个权值更小的mst。

哎，自己还想到这里了，不过立马就否决了。。

首先排序，对权值相同的边一起考虑。如果当前边所连的联通块已经被合并，那么该边一定不在mst上。这样就解决了第三种情况

考虑剩下的边，要么一定在mst上，要么可能在mst上。

如果一定在mst上，显然断开它之后会形成两个联通块。这与“桥”的定义相同！所以tarjan一遍求出所有桥就行了。

如果每次都tarjan的话显然会t飞，因此我们把在一个联通块内的点缩起来就行了

#include<bits/stdc++.h> #define pair pair<int, int> #define mp(x, y) make_pair(x, y) #define fi first #define se second using namespace std; const int maxn = 2e5 + 10; inline int read() {     char c = getchar(); int x = 0, f = 1;     while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}     while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();     return x * f; } int n, m; vector<pair> v[maxn]; struct edge {     int u, v, w, f, id;     bool operator < (const edge &rhs) const {         return w < rhs.w;     } }e[maxn]; int dfn[maxn], low[maxn], tot, fa[maxn], ans[maxn]; void tarjan(int x, int fa) {//这里的fa表示边的编号     dfn[x] = low[x] = ++tot;     for(int i = 0, to, id; i < v[x].size(); i++) {         if((id = v[x][i].se) == fa) continue;         to = v[x][i].fi;         if(!dfn[to]) {             tarjan(to, id), low[x] = min(low[x], low[to]);             if(low[to] > dfn[x]) e[id].f = 2;         }         else low[x] = min(low[x], dfn[to]);     } }  int find(int x) {     return x == fa[x] ? fa[x] : fa[x] = find(fa[x]); }  int main() {     n = read(), m = read();     for(int i = 1; i <= n; i++) fa[i] = i;     for(int i = 1; i <= m; i++) {         int x = read(), y = read(), z = read();         e[i] = (edge) {x, y, z, 0, i};     }     sort(e + 1, e + m + 1);     int nxt;     for(int i = 1; i <= m; i = nxt + 1) {         nxt = i + 1;         for(; e[i].w == e[nxt].w; nxt++); nxt--;         for(int j = i; j <= nxt; j++) {             int x = find(e[j].u), y = find(e[j].v);             if(x == y) continue;             v[x].push_back(mp(y, j));             v[y].push_back(mp(x, j));              e[j].f = 1;//maybe         }         for(int j = i; j <= nxt; j++) {             int x = find(e[j].u), y = find(e[j].v);             if(x == y || dfn[x]) continue;             tarjan(x, -1);         }         for(int j = i; j <= nxt; j++) {             int x = find(e[j].u), y = find(e[j].v);             if(x == y) continue;             v[x].clear(); v[y].clear();             dfn[x] = 0; dfn[y] = 0;             fa[x] = y;         }     }     for(int i = 1; i <= m; i++) ans[e[i].id] = e[i].f;     for(int i = 1; i <= m; i++) {         if(ans[i] == 0) puts("none");         else if(ans[i] == 1) puts("at least one");         else puts("any");     }     return 0; } /*  */