YZOJ P3049 [SHOI2010]Minimum Spanning Tree
时间限制：1000MS 内存限制：262144KB
难度：\(6.0\)
-
题目描述
有一个 \(n\) 个点，\(m\) 条边的无向图，每次可以对这张图进行操作：对于一条边 \((u,v)\)，可以把图中除了这条边以外的边，每一条的权值都减少 \(1\)。
对于某一条编号为 \(e\) 的边，至少需要多少次操作，才能保证其能出现在最小生成树中？
-
输入格式
第一行输入三个整数 \(n\)、\(m\)、\(e\)。
接下来输入 \(m\) 行，每行输入三个整数，其中第 \(i+1\) 行输入的整数分别为 \(u_i\)、\(v_i\)、\(w_i\)，表示无向图的边的两个端点和边权。
-
输出格式
输出一个整数表示答案。
-
样例输入
|
1 2 3 4 5 6 7 8 9 |
5 8 8 5 1 1 5 2 2 5 3 5 5 4 7 1 2 0 2 3 15 2 4 25 1 4 100 |
-
样例输出
|
1 |
170 |
-
数据规模与约定
对于 \(50\%\) 的数据，\(n \leq 300\)，\(m \leq 1000\) 。
对于 \(100\%\) 的数据，\(n \leq 2 \times 10^4\)，\(m \leq 2 \times 10^5\)，\(0 \leq w_i \leq 2\times 10^4\) 。
考虑 Kruskal 算法，边 \(e\) 出现在最小生成树中，当且仅当权值比它小的边全部加进去时，仍然不能使得 \(e\) 的两端点连通。
所以就有了一个做法，把权值比它小的边全部弄成比它大，代价就是权值的差值，要割掉权值和尽量小的一些边，使得 \(e\) 的两端点不连通。
发现这是一个最小割模型。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 |
// Powered by C4droid with GCCv7.2.0 #include <cstdio> #include <cstdlib> #include <cstring> #include <climits> #define INFINITE 0x7F7F7F7F #define _min(_a_,_b_) ((_a_)<(_b_)?(_a_):(_b_)) inline int getnum() { register char c=0; while(!(c>='0' && c<='9')) c=getchar(); register int a=0; while(c>='0' && c<='9') a=a*10+c-'0',c=getchar(); return a; } #define GetReverse(_x) ((_x)&1 ? (_x)+1 : (_x)-1) int gcnt,ghead[20505],gnext[805050],gnode[805050],gflow[805050]; inline void insertLine(register int s,register int t,const int&v) { gnext[++gcnt]=ghead[s],ghead[s]=gcnt,gnode[gcnt]=t,gflow[gcnt]=v; gnext[++gcnt]=ghead[t],ghead[t]=gcnt,gnode[gcnt]=s,gflow[gcnt]=0; } int S,T; int dist[20505]; inline bool BFS() { static int lst[20505]; register int front=0,rear=0; memset(dist,0,sizeof(dist)); dist[S]=1,lst[rear++]=S; while(front<rear) { register int now=lst[front++]; for(register int j=ghead[now],t;j;j=gnext[j]) if(gflow[j]>0 && !dist[t=gnode[j]]) dist[t]=dist[now]+1,lst[rear++]=t; } return dist[T]; } int cur[20505]; int DFS(register int now,register int mxflow) { if(now == T) return mxflow; for(register int j=cur[now],t;j;j=gnext[j]) { cur[now]=j,t=gnode[j]; if(!(gflow[j]>0 && dist[t]==dist[now]+1)) continue; register int nf=DFS(t,_min(mxflow,gflow[j])); if(nf) { gflow[j]-=nf; gflow[GetReverse(j)]+=nf; return nf; } } return 0; } int es[205050],et[205050],ew[205050]; int main() { register int N=getnum(),M=getnum(),E=getnum(); for(register int i=1;i<=M;i++) es[i]=getnum(),et[i]=getnum(),ew[i]=getnum(); for(register int i=1;i<=M;i++) if(i!=E && ew[i]<=ew[E]) { insertLine(es[i],et[i],ew[E]-ew[i]+1); insertLine(et[i],es[i],ew[E]-ew[i]+1); } S=es[E],T=et[E]; register int ans=0; while(BFS()) { for(register int i=1;i<=N;i++) cur[i]=ghead[i]; while(int nf=DFS(S,INFINITE)) ans+=nf; } printf("%d\n",ans); return 0; } |