cf160D. Edges in MST(最小生成树 桥)
程序员文章站
2022-06-22 11:59:56
题意 "题目链接" 给出一棵树,确定每条边状态: 一定在MST上 / 可能在MST上 / 不可能在MST上 $n \leqslant 10^5, m \leqslant 10^5$ Sol MST表示最小生成树 表示只能想到$nlog^2n$的做法:先求出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; } /* */
推荐阅读
-
图论小结(一)包括一些最短路,最小生成树,差分约束,欧拉回路,的经典题和变种题。强连通,双连通,割点割桥的应用。二分匹配
-
G. Xor-MST(异或最小生成树)
-
cf888G. Xor-MST(Boruvka最小生成树 Trie树)
-
【bzoj1937】[Shoi2004]Mst 最小生成树
-
cf160D. Edges in MST(最小生成树 桥)
-
图论小结(一)包括一些最短路,最小生成树,差分约束,欧拉回路,的经典题和变种题。强连通,双连通,割点割桥的应用。二分匹配
-
G. Xor-MST(异或最小生成树)
-
cf888G. Xor-MST(Boruvka最小生成树 Trie树)
-
cf160D. Edges in MST(最小生成树 桥)