\(n\)个点\(m\)条带权边的无向连通图\(G\),记\(G\)的最小生成树集合\(minTree\),求满足\(edge \in minTree_i(1\leq i \leq size(minTree))\)的条数。(既这条边要在\(G\)的所有最小生成树中出现)
\(2 \leq n <m\leq2* 10^5\),\(1 \leq w \leq 10^6\)
考虑相同权值的边对最小生成树造成的影响。将边排序后,记\(w_i\)为当前要加的边的权值,\(G’\)为使用权值\(w_j(1\leq j \leq i - 1)\)的边依照kruskal算法构成的图。那么向\(G‘\)加入所有\(w_x = w_i\)的边而构成的图\(G‘‘\)的桥就是出现在所有最小生成树中的边,然后不断以递推的形式就能求解。
1.\(G‘\)可能有很多个,那么选择某个\(G‘\)是否对\(G‘‘\)的桥的个数会有影响?
? 不会,记权值为\(w_i\)的边的两个端点为\(u,v\),\(G‘\)的顶点集合为\(S\),如果\(u \in S, v \in S\),那么无论是哪个\(G‘\),这条边都不会加入\(G‘\)去构成\(G‘‘\)。如果不都属于\(S\),那么这条边与\(G‘\)中边没有任何关系,既无论是哪个\(G‘\)都不会对\(G‘‘\)造成影响。
2.如果每加入一组权值为\(w_i\)的边,都求一次图\(G‘‘\)的桥,会不会超时?
? 显然会超时,由1得,新加的边与\(G‘\)没有关系,所以可以将\(G‘\)的各个连通分支压缩成一个点。然后建图,跑完Tarjan,再删除原来的图。
const int N = 200050;
struct Edge { int u, v, w; } e[N];
struct node { int to, next, id; } G[N << 1];
int n, m, p, tot, cnt;
int fa[N], Low[N], Dfn[N], res[N], head[N];
bool cmp(Edge& a, Edge& b) { return a.w < b.w; }
void Inite() {
cnt = tot = 0;
mem(head, -1);
rep(i, 1, N) fa[i] = i;
}
void addedge(int u, int v, int id) {
G[tot].to = v, G[tot].id = id, G[tot].next = head[u], head[u] = tot++;
G[tot].to = u, G[tot].id = id, G[tot].next = head[v], head[v] = tot++;
}
void Tarjan(int u, int last) {
Low[u] = Dfn[u] = ++cnt;
for (int i = head[u]; ~i; i = G[i].next) if (i != (1 ^ last)) {
int v = G[i].to;
if (Dfn[v]) Low[u] = min(Low[u], Dfn[v]);
else {
Tarjan(v, i);
Low[u] = min(Low[u], Low[v]);
if (Dfn[u] < Low[v]) res[G[i].id] = 1;
}
}
}
int Find(int a) {
return (a == fa[a] ? a : (fa[a] = Find(fa[a])));
}
void Solve() {
for (int i = 1, j = 1; i <= m; i = j, tot = 0) {
while(e[j].w == e[i].w) ++j;
rep(k, i, j) {
int fu = Find(e[k].u), fv = Find(e[k].v);
if (fu != fv) addedge(fu, fv, k);
}
rep(k, i, j) {
int fu = Find(e[k].u), fv = Find(e[k].v);
if ((fu != fv) && !Dfn[fu]) Tarjan(fu, -1);
}
rep(k, i, j) {
int fu = Find(e[k].u), fv = Find(e[k].v);
Dfn[fu] = Dfn[fv] = 0;
head[fu] = head[fv] = -1;
if (fu != fv) fa[fu] = fv;
}
}
int ans = 0;
Rep(i, 1, m) ans += res[i];
pr(ans);
}
int main()
{
Inite();
IOS;
cin >> n >> m >> p;
Rep(i, 1, m) cin >> e[i].u >> e[i].v >> e[i].w;
sort(e + 1, e + m + 1, cmp);
Solve();
return 0;
}
原文:https://www.cnblogs.com/zgglj-com/p/10086341.html