Description
给出一个 N 个点 M 条边的无向带权图, 以及 Q 个询问, 每次询问在图中删掉一条边后图的最小生成树.(各询问间独立, 每次询问不对之后的询问产生影响, 即被删掉的边在下一条询问中依然存在)
Input
第一行两个正整数 N,M(N<=50000,M<=100000) 表示原图的顶点数和边数.
下面 M 行, 每行三个整数 X,Y,W 描述了图的一条边 (X,Y), 其边权为 W(W<=10000). 保证两点之间至多只有一条边.
接着一行一个正整数 Q, 表示询问数.(1<=Q<=100000)
下面 Q 行, 每行一个询问, 询问中包含一个正整数 T, 表示把编号为 T 的边删掉 (边从 1 到 M 按输入顺序编号).
Output
Q 行, 对于每个询问输出对应最小生成树的边权和的值, 如果图不连通则输出 "Not connected"
- Sample Input
- 4 4
- 1 2 3
- 1 3 5
- 2 3 9
- 2 4 1
- 4
- 1
- 2
- 3
- 4
- Sample Output
- 15
- 13
- 9
- Not connected
样例解释:
无
数据规模:
10% 的数据 N,M,Q<=100.
另外 30% 的数据, N<=1000
100% 的数据如题目.
提供一种堆 + 启发式合并的做法
首先 , 明确一点删掉一条不在最小生成树上的边 , 删去之后没有影响.
那考虑 , 删去一个不是树上的边 , 会有哪些边进行替补.
我们将每个非树边的边权 , 放到点上 , 再在两个点的树上的 LCA 处存一下这个边权表示 , 这个边的贡献在 LCA 处消失 . 注意 存到点上的边权是说明这条边可以替补这个点上面的边 . (不能是下面的边 , 因为一个节点可能有若干个儿子 , 也就是不确定表示的是哪一个);
对每个节点维护一个堆 , 在 dfs 一遍 , 将边权不断向上合并, 并减去存在该点应该减去的东西 , 那么替换这个点上面的那个边的最小值就是堆中的最小值.
对了 堆是可删除滴 , 在维护一个就是了.
- #include<iostream>
- #include<algorithm>
- #include<cstdio>
- #include<queue>
- #include<vector>
- using namespace std;
- const int N = 51000;
- const int M = 101000;
- inline int read()
- {
- register int x = 0; register char c = getchar();
- while(c <'0' || c> '9') c = getchar();
- while(c>= '0' && c <= '9') x = (x <<3) + (x << 1) + c - '0' , c = getchar();
- return x;
- }
- int n , m , cnt;
- int head[N] , pos[M] , fa[N] , d[N] , root[N] , f[N][17] , ans[N] , vis[M];
- struct edge{ int u , v , c , id; } ed[M];
- struct node{ int v , nex , c; } e[M<<1];
- vector<int> vt[N];
- struct Heap
- {
- priority_queue<int , vector<int> , greater<int>> A , B;
- inline void push(int x) { A.push(x); }
- inline void del(int x) { B.push(x); }
- inline int siz() { return A.size() - B.size(); }
- inline int top()
- {
- while(B.size() && A.top() == B.top()) A.pop() , B.pop();
- return A.top();
- }
- }q[N];
- inline bool cmp(const edge &A , const edge &B) { return A.c <B.c; }
- inline void add(int u , int v , int c) { e[++cnt].v = v; e[cnt].c = c; e[cnt].nex = head[u]; head[u] = cnt; return ; }
- int find(int x) { return x == fa[x] ? x : fa[x] = find(fa[x]); }
- void dfs(int x , int fa)
- {
- d[x] = d[fa] + 1;
- for(int i = 1 ; i <= 16 ; ++i) f[x][i] = f[f[x][i-1]][i-1];
- for(int i = head[x] , v; i ; i = e[i].nex)
- {
- v = e[i].v; if(v == fa) continue;
- f[v][0] = x; dfs(v , x);
- }
- }
- int LCA(int x , int y)
- {
- if(x == y) return x;
- if(d[x] < d[y]) swap(x , y);
- for(int i = 16 ; i>= 0 ; --i) if(d[f[x][i]]>= d[y]) x = f[x][i];
- if(x == y) return x;
- for(int i = 16 ; i>= 0 ; --i) if(f[x][i] != f[y][i]) x = f[x][i] , y = f[y][i];
- return f[x][0];
- }
- void dfs(int x)
- {
- for(int i = head[x] , v; i ; i = e[i].nex)
- {
- v = e[i].v; if(v == f[x][0]) continue;
- dfs(v);
- if(q[root[x]].siz() <q[root[v]].siz()) swap(root[x] , root[v]);
- while(q[root[v]].siz()) q[root[x]].push(q[root[v]].top()) , q[root[v]].del(q[root[v]].top());
- }
- for(int i = 0 , s = vt[x].size() ; i < s ; ++i) q[root[x]].del(vt[x][i]) , q[root[x]].del(vt[x][i]);
- ans[x] = q[root[x]].siz()> 0 ? q[root[x]].top() : -1;
- return ;
- }
- int main()
- {
- n = read(); m = read();
- for(int i = 1 ; i <= m ; ++i)
- ed[i].u = read() ,
- ed[i].v = read() ,
- ed[i].c = read() ,
- ed[i].id = i ;
- sort(ed + 1 , ed + 1 + m , cmp);
- // for(int i = 1 ; i <= m ; ++i) printf("ed[%d].val = %d\n" , i , ed[i].c);
- for(int i = 1 ; i <= n ; ++i) fa[i] = i , root[i] = i;
- long long Ans = 0;
- for(int i = 1 , x , y; i <= m ; ++i)
- {
- pos[ed[i].id] = i; x = find(ed[i].u); y = find(ed[i].v);
- if(x == y) continue;
- else fa[x] = y , Ans += ed[i].c , add(ed[i].u, ed[i].v , ed[i].c) , add(ed[i].v , ed[i].u , ed[i].c) , vis[i] = 1;
- }
- // puts("RRRRRRRRRRRRRRRRRRRRRRRRRRRR");
- // cout <<Ans << endl;
- // puts("QQQQQQQQQQQQQQQQQQQQQQQQQQQQ");
- if(cnt != (n - 1) * 2)
- {
- int Q = read();
- while(Q --) puts("Not connected");
- return 0;
- }
- dfs(1 , 0);
- for(int i = 1 , j , a , b , c ; i <= m ; ++i) if(!vis[i])
- {
- j = pos[ed[i].id];
- a = ed[j].u; b = ed[j].v; c = ed[j].c;
- q[a].push(c); q[b].push(c); vt[LCA(a , b)].push_back(c);
- }
- dfs(1); int Q = read();
- for(int i = 1 , x ; i <= Q ; ++i)
- {
- x = pos[read()];
- if(!vis[x]) printf("%d\n" , Ans);
- else
- {
- int a = ed[x].u , b = ed[x].v;
- b = d[b]> d[a] ? b : a;
- if(ans[b] == -1) puts("Not connected");
- else printf("%d\n" , Ans - ed[x].c + ans[b]);
- }
- }
- return 0;
- }
- /*
- 4 4
- 1 2 3
- 1 3 5
- 2 3 9
- 2 4 1
- 4
- 1
- 2
- 3
- 4
- */
来源: http://www.bubuko.com/infodetail-3374865.html