首页 > 代码库 > BZOJ-2561-最小生成树 题解（最小割）

BZOJ-2561-最小生成树 题解（最小割）

2024-08-30 23:46:53   218人阅读

2561: 最小生成树（题解）

Time Limit: 10 Sec  Memory Limit: 128 MB
Submit: 1628  Solved: 786

传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=2561

Description

　给定一个边带正权的连通无向图G=(V,E)，其中N=|V|，M=|E|，N个点从1到N依次编号，给定三个正整数u，v，和L (u≠v)，假设现在加入一条边权为L的边(u,v)，那么需要删掉最少多少条边，才能够使得这条边既可能出现在最小生成树上，也可能出现在最大生成树上？

Input

第一行包含用空格隔开的两个整数，分别为N和M；
接下来M行，每行包含三个正整数u，v和w表示图G存在一条边权为w的边(u,v)。
最后一行包含用空格隔开的三个整数，分别为u，v，和 L；
数据保证图中没有自环。

Output

输出一行一个整数表示最少需要删掉的边的数量。

Sample Input

3 2
3 2 1
1 2 3
1 2 2

Sample Output

1

HINT

对于20%的数据满足N ≤ 10，M ≤ 20，L ≤ 20；

对于50%的数据满足N ≤ 300，M ≤ 3000，L ≤ 200；

对于100%的数据满足N ≤ 20000，M ≤ 200000，L ≤ 20000。

 
【解析】
我们首先回忆一下kruskal算法求MST。。。
然后反过来想：如果一条边在MST上，那么权值小于它的边肯定做不出一个生成树。
之后就简单了：对于在最小生成树上，肯定是要在权值小于它的边中删掉一些使得剩下的不能做成一个生成树，也就是使要加入的边的两个端点在图中不连通。
我们想到了最小割！
要加入的边的两个端点分别是源与汇，然后每条小于其的边（注意：这是在MST上，在最大生成树上也同理，即处理大于它的边）的两个端点在图中连一条权值为1的无向边。然后最小割即可。
最终将在最小生成树与最大生成树上的处理的最小割的值相加即为所求。
我的程序452 MS，目前进排行榜前15啦～
技术分享 
  1 #include<iostream>
  2 #include<fstream>
  3 #include<cstdio>
  4 #include<algorithm>
  5 #include<string>
  6 #include<vector>
  7 #include<queue>
  8 #include<deque>
  9 #include<utility>
 10 #include<map>
 11 #include<set>
 12 #include<cmath>
 13 #include<cstdlib>
 14 #include<ctime>
 15 #include<functional>
 16 #include<sstream>
 17 #include<cstring>
 18 #include<bitset>
 19 #include<stack>
 20 using namespace std;
 21 
 22 int n,m,s,t,cnt,x,y,z,ansx,l;
 23 struct sdt
 24 {
 25     int cap,flow,u,v;
 26 }e[400005];
 27 struct bdq
 28 {
 29     int a,b,c;
 30 }edge[200005];
 31 int nxt[400005],fir[20005],d[20005],par[20005],num[20005],cur[20005];
 32 bool vis[20005];
 33 
 34 int read()
 35 {
 36     int x=0;char c=getchar();
 37     while(c<48||c>57)c=getchar();
 38     while(c>47&&c<58)x*=10,x+=c-48,c=getchar();
 39     return x;
 40 }
 41 
 42 void bfs()
 43 {
 44     memset(vis,0,sizeof(vis));
 45     memset(d,0,sizeof(d));
 46     queue<int>q;
 47     d[t]=0;
 48     vis[t]=1;
 49     q.push(t);
 50     while(!q.empty())
 51     {
 52         int k=q.front();
 53         q.pop();
 54         for(int i=fir[k];i;i=nxt[i])
 55         {
 56             if(!vis[e[i].v])
 57             {
 58                 vis[e[i].v]=1;
 59                 d[e[i].v]=d[k]+1;
 60                 q.push(e[i].v);
 61             }
 62         }
 63     }
 64 }
 65 
 66 int agument()
 67 {
 68     int p=t;
 69     int ans=2147483647;
 70     while(p!=s)
 71     {
 72         ans=min(ans,e[par[p]].cap-e[par[p]].flow);
 73         p=e[par[p]].u;
 74     }
 75     p=t;
 76     while(p!=s)
 77     {
 78         e[par[p]].flow+=ans;
 79         e[par[p]^1].flow-=ans;
 80         p=e[par[p]].u;
 81     }
 82     return ans;
 83 }
 84 
 85 int isap()
 86 {
 87     memset(num,0,sizeof(num));
 88     int flow=0;
 89     for(int i=1;i<=n;i++)
 90     {
 91         num[d[i]]++;
 92         cur[i]=fir[i];
 93     }
 94     int p=s;
 95     while(d[s]<n)
 96     {
 97         if(p==t)
 98         {
 99             flow+=agument();
100             p=s;
101         }
102         bool ok=0;
103         for(int i=cur[p];i;i=nxt[i])
104         {
105             if(e[i].cap>e[i].flow && d[p]==d[e[i].v]+1)
106             {  
107                 ok=1;  
108                 par[e[i].v]=i;  
109                 cur[p]=i;  
110                 p=e[i].v;  
111                 break;  
112             }  
113         }
114         if(!ok)
115         {
116             int mn=n-1;
117             for(int i=fir[p];i;i=nxt[i])
118             {
119                 if(e[i].cap>e[i].flow)mn=min(mn,d[e[i].v]);
120             }
121             if(--num[d[p]]==0)break;
122             num[d[p]=mn+1]++;
123             cur[p]=fir[p];
124             if(p!=s)p=e[par[p]].u;
125         }
126     }
127     return flow;
128 }
129 
130 int main()
131 {
132     memset(nxt,0,sizeof(nxt));
133     memset(fir,0,sizeof(fir));
134     n=read();m=read();
135     cnt=1;
136     for(int i=1;i<=m;i++)
137     {
138         edge[i].a=read();edge[i].b=read();edge[i].c=read();
139     }
140     s=read();t=read();l=read();
141     for(int i=1;i<=m;i++)
142     {
143         if(edge[i].c<l)
144         {
145             x=edge[i].a;
146             y=edge[i].b;
147             e[++cnt].u=x;e[cnt].v=y;e[cnt].cap=1;e[cnt].flow=0;
148             nxt[cnt]=fir[x];fir[x]=cnt;
149             e[++cnt].u=y;e[cnt].v=x;e[cnt].cap=1;e[cnt].flow=0;
150             nxt[cnt]=fir[y];fir[y]=cnt;
151         }
152     }
153     bfs();
154     ansx+=isap();
155     cnt=1;
156     memset(nxt,0,sizeof(nxt));
157     memset(fir,0,sizeof(fir));
158     memset(e,0,sizeof(e));
159     for(int i=1;i<=m;i++)
160     {
161         if(edge[i].c>l)
162         {
163             x=edge[i].a;
164             y=edge[i].b;
165             e[++cnt].u=x;e[cnt].v=y;e[cnt].cap=1;e[cnt].flow=0;
166             nxt[cnt]=fir[x];fir[x]=cnt;
167             e[++cnt].u=y;e[cnt].v=x;e[cnt].cap=1;e[cnt].flow=0;
168             nxt[cnt]=fir[y];fir[y]=cnt;
169         }
170     }
171     bfs();
172     ansx+=isap();
173     printf("%d\n",ansx);
174     return 0;
175 }
ISAP实现

 

BZOJ-2561-最小生成树 题解（最小割）


联系
我们