[关闭]
@lpf20051024 2020-08-11T14:51:04.000000Z 字数 9166 阅读 695

网络流 24 题

网络流 题解

前言

都是从 cnblog 来的吧，代码就贴在这里啦。

配合 原讲解+少量注释 食用更佳。

飞行员配对方案问题

  1. #include<cstdio>
  2. #include<cstring>
  3. #include<algorithm>
  4. #include<iostream>
  5. #include<cmath>
  6. #include<queue>
  7. #define N 110
  8. #define M 100100
  9. using namespace std;
  11. int n,m,head[N],match[N],cnt=0,ans=0;
  12. bool vis[N];
  13. struct Edge{
  14.     int nxt,to;
  15. }ed[M];
  17. int read(){
  18.     int x=0,f=1;char c=getchar();
  19.     while(c<'0' || c>'9') f=(c=='-')?-1:1,c=getchar();
  20.     while(c>='0' && c<='9') x=x*10+c-48,c=getchar();
  21.     return x*f;
  22. }
  24. void add(int u,int v){
  25.     ed[++cnt].nxt=head[u];
  26.     ed[cnt].to=v;
  27.     head[u]=cnt;
  28.     return;
  29. }
  31. bool dfs(int u){
  32.     for(int i=head[u];i;i=ed[i].nxt){
  33.         int v=ed[i].to;
  34.         if(vis[v]) continue;
  35.         vis[v]=true;
  36.         if(!match[v] || dfs(match[v])){
  37.             match[v]=u;return true;
  38.         }
  39.     }
  40.     return false;
  41. }
  43. int main(){
  44.     n=read(),m=read()-n;
  45.     int u=read(),v=read();
  46.     while(u!=-1 && v!=-1){
  47.         add(u,v),add(v,u);
  48.         u=read(),v=read();
  49.     }
  50.     for(int i=1;i<=n;i++){
  51.         memset(vis,false,sizeof(vis));
  52.         if(dfs(i)) ++ans;
  53.     }
  54.     printf("%d\n",ans);
  55.     for(int i=n+1;i<=n+m;i++)
  56.         if(match[i]) printf("%d %d\n",match[i],i);
  57.     return 0;
  58. }

圆桌问题

  1. #include<cstdio>
  2. #include<cstring>
  3. #include<cmath>
  4. #include<iostream>
  5. #include<algorithm>
  6. #include<queue>
  7. #define N 1010
  8. #define M 100010
  9. #define INF 0x3f3f3f3f 
  10. using namespace std;
  12. int n,m,s,t,sum=0,head[N],d[N],cnt=1;
  13. struct Edge{
  14.     int nxt,to,val;
  15. }ed[M<<1];
  16. queue<int>q;
  18. int read(){
  19.     int x=0,f=1;char c=getchar();
  20.     while(c<'0' || c>'9') f=(c=='-')?-1:1,c=getchar();
  21.     while(c>='0' && c<='9') x=x*10+c-48,c=getchar();
  22.     return x*f;
  23. }
  25. void add(int u,int v,int w){
  26.     ed[++cnt].nxt=head[u];ed[cnt].to=v;ed[cnt].val=w;head[u]=cnt;
  27.     ed[++cnt].nxt=head[v];ed[cnt].to=u;ed[cnt].val=0;head[v]=cnt;
  28. }
  30. bool bfs(){
  31.     memset(d,0,sizeof(d));
  32.     while(!q.empty()) q.pop();
  33.     d[s]=1;q.push(s);
  34.     while(!q.empty()){
  35.         int u=q.front();q.pop();
  36.         for(int i=head[u];i;i=ed[i].nxt){
  37.             int v=ed[i].to,w=ed[i].val;
  38.             if(w && !d[v]){
  39.                 d[v]=d[u]+1;
  40.                 if(v==t) return true;
  41.                 q.push(v);
  42.             }
  43.         }
  44.     }
  45.     return false;
  46. }
  48. int dinic(int u,int flow){
  49.     if(u==t) return flow;
  50.     int rest=flow;
  51.     for(int i=head[u];i && rest;i=ed[i].nxt){
  52.         int v=ed[i].to,w=ed[i].val;
  53.         if(w && d[v]==d[u]+1){
  54.             int k=dinic(v,min(rest,w));
  55.             if(!k) d[v]=0;
  56.             ed[i].val-=k;
  57.             ed[i^1].val+=k;
  58.             rest-=k;
  59.         }
  60.     }
  61.     return flow-rest;
  62. }
  64. int main(){
  65.     n=read(),m=read();
  66.     s=0,t=n+m+1;
  67.     for(int i=1;i<=n;i++){
  68.         int a=read();sum+=a;//记录代表总数。
  69.         add(s,i,a);
  70.     }
  71.     for(int i=1;i<=m;i++){
  72.         int a=read();
  73.         add(i+n,t,a);
  74.     }
  75.     for(int i=1;i<=n;i++)
  76.         for(int j=1;j<=m;j++)
  77.             add(i,j+n,1);
  78.     int ans=0,flow;
  79.     while(bfs())
  80.         if(flow=dinic(s,INF)) ans+=flow;
  81.     if(ans<sum){puts("0");return 0;}
  82.     puts("1");
  83.     for(int u=1;u<=n;u++){
  84.         for(int i=head[u];i;i=ed[i].nxt){
  85.             int v=ed[i].to,w=ed[i].val;
  86.             if(v!=s && !w) printf("%d ",v-n);//根据残量网络输出。
  87.         }
  88.         puts("");
  89.     }
  90.     return 0;
  91. }

最小路径覆盖问题

  1. #include<cstdio>
  2. #include<cstring>
  3. #include<cmath>
  4. #include<algorithm>
  5. #include<iostream>
  6. #include<queue>
  7. #define N 510
  8. #define M 100010
  9. #define INF 0x3f3f3f3f
  10. using namespace std;
  12. int n,m,s,t,head[N],fa[N],d[N],cnt=1;
  13. struct Edge{
  14.     int nxt,frm,to,val;
  15. }ed[M];
  16. queue<int>q;
  18. int read(){
  19.     int x=0,f=1;char c=getchar();
  20.     while(c<'0' || c>'9') f=(c=='-')?-1:1,c=getchar();
  21.     while(c>='0' && c<='9') x=x*10+c-48,c=getchar();
  22.     return x*f;
  23. }
  25. void add(int u,int v,int w){
  26.     ed[++cnt]=(Edge){head[u],u,v,w};head[u]=cnt;
  27.     ed[++cnt]=(Edge){head[v],v,u,0};head[v]=cnt;
  28. }
  30. void build(){//建图。
  31.     n=read(),m=read();
  32.     s=0,t=n<<1|1;
  33.     for(int i=1;i<=m;i++){
  34.         int u=read(),v=read();
  35.         add(u,v+n,1);
  36.     }
  37.     for(int i=1;i<=n;i++) add(s,i,1);
  38.     for(int i=1;i<=n;i++) add(i+n,t,1);
  39.     return;
  40. }
  42. bool bfs(){
  43.     while(!q.empty()) q.pop();
  44.     memset(d,0,sizeof(d));
  45.     d[s]=1;q.push(s);
  46.     while(!q.empty()){
  47.         int u=q.front();q.pop();
  48.         for(int i=head[u];i;i=ed[i].nxt){
  49.             int v=ed[i].to,w=ed[i].val;
  50.             if(w && !d[v]){
  51.                 d[v]=d[u]+1;
  52.                 if(v==t) return true;
  53.                 q.push(v);
  54.             }
  55.         }
  56.     }
  57.     return false;
  58. }
  60. int Dinic(int u,int flow){
  61.     if(u==t) return flow;
  62.     int rest=flow;
  63.     for(int i=head[u];i && rest;i=ed[i].nxt){
  64.         int v=ed[i].to,w=ed[i].val;
  65.         if(w && d[v]==d[u]+1){
  66.             int k=Dinic(v,min(rest,w));
  67.             if(!k) d[v]=0;
  68.             ed[i].val-=k;
  69.             ed[i^1].val+=k;
  70.             rest-=k;
  71.         }
  72.     }
  73.     return flow-rest;
  74. }
  76. int find(int x){
  77.     if(fa[x]==x) return x;
  78.     return fa[x]=find(fa[x]);
  79. }
  81. void Print(int u){
  82.     printf("%d ",u);
  83.     for(int i=head[u];i;i=ed[i].nxt)
  84.         if(!ed[i].val && ed[i].to>n)
  85.             Print(ed[i].to-n);//递归输出。
  86.     return;
  87. }
  89. void work(){
  90.     int flow,ans=0;
  91.     while(bfs())
  92.         if(flow=Dinic(s,INF)) ans+=flow;
  93.     for(int i=1;i<=n;i++) fa[i]=i;
  94.     for(int i=2;i<=cnt;i++){
  95.         int u=ed[i].frm,v=ed[i].to,w=ed[i].val;
  96.         if(u>s && u<=n && v>n && v<t && !w)//找到被匹配了的边，表示这两点被合并了。
  97.             fa[find(v-n)]=find(u);
  98.         //与一般并查集不同的是 v-n 和 u 的顺序不可调换。
  99.         //因为 u 在路径上的位置必然在 v-n 之前，而路径的输出需要考虑递归的顺序。
  100.     }
  101.     for(int i=1;i<=n;i++)
  102.         if(fa[i]==i) Print(i),puts("");
  103.     printf("%d\n",n-ans);
  104.     return;
  105. }
  107. int main(){
  108.     build();
  109.     work();
  110.     return 0;
  111. }

试题库问题

  1. //真就是一道挺板子的题目啊。
  2. #include<cstdio>
  3. #include<cstring>
  4. #include<iostream>
  5. #include<cmath>
  6. #include<algorithm>
  7. #include<queue>
  8. #define N 10010
  9. #define M 200010
  10. #define INF 0x3f3f3f3f
  11. using namespace std;
  13. int m,n,s,t,head[N],d[N],cnt=1;
  14. struct Edge{
  15.     int nxt,to,val;
  16. }ed[M];
  17. queue<int>q;
  19. int read(){
  20.     int x=0,f=1;char c=getchar();
  21.     while(c<'0' || c>'9') f=(c=='-')?-1:1,c=getchar();
  22.     while(c>='0' && c<='9') x=x*10+c-48,c=getchar();
  23.     return x*f;
  24. }
  26. void add(int u,int v,int w){
  27.     ed[++cnt]=(Edge){head[u],v,w};head[u]=cnt;
  28.     ed[++cnt]=(Edge){head[v],u,0};head[v]=cnt;
  29.     return;
  30. }
  32. bool bfs(){
  33.     while(!q.empty()) q.pop();
  34.     memset(d,0,sizeof(d));
  35.     d[s]=1;q.push(s);
  36.     while(!q.empty()){
  37.         int u=q.front();q.pop();
  38.         for(int i=head[u];i;i=ed[i].nxt){
  39.             int v=ed[i].to,w=ed[i].val;
  40.             if(w && !d[v]){
  41.                 d[v]=d[u]+1;
  42.                 if(v==t) return true;
  43.                 q.push(v);
  44.             }
  45.         }
  46.     }
  47.     return false;
  48. }
  50. int Dinic(int u,int flow){
  51.     if(u==t) return flow;
  52.     int rest=flow;
  53.     for(int i=head[u];i && rest;i=ed[i].nxt){
  54.         int v=ed[i].to,w=ed[i].val;
  55.         if(w && d[v]==d[u]+1){
  56.             int k=Dinic(v,min(rest,w));
  57.             if(!k) d[v]=0;
  58.             ed[i].val-=k;
  59.             ed[i^1].val+=k;
  60.             rest-=k;
  61.         }
  62.     }
  63.     return flow-rest;
  64. }
  66. int main(){
  67.     n=read(),m=read();
  68.     int a,b,sum=0;
  69.     s=0,t=n+m+1;
  70.     for(int i=1;i<=n;i++)
  71.         a=read(),sum+=a,add(s,i,a);
  72.     for(int i=1;i<=m;i++){
  73.         a=read();
  74.         while(a--) b=read(),add(b,i+n,1);
  75.     }
  76.     for(int i=1;i<=m;i++) 
  77.         add(i+n,t,1);
  78.     int ans=0,flow;
  79.     while(bfs())
  80.         if(flow=Dinic(s,INF)) ans+=flow;
  81.     if(ans<sum){
  82.         puts("No Solution!");return 0;
  83.     }
  84.     for(int u=1;u<=n;u++){
  85.         printf("%d: ",u);
  86.         for(int i=head[u];i;i=ed[i].nxt)
  87.             if(!ed[i].val && ed[i].to>n) printf("%d ",ed[i].to-n);
  88.         puts("");
  89.     }
  90.     return 0;
  91. }

魔术球问题

  1. #include<cstdio>
  2. #include<cstring>
  3. #include<iostream>
  4. #include<algorithm>
  5. #include<queue>
  6. #include<cmath>
  7. #define N 1000010
  8. #define M 2000010
  9. #define s 0
  10. #define t 1000000
  11. #define INF 0x3f3f3f3f
  12. using namespace std;
  14. int n,head[N],frs[N],pre[N],d[N],cnt=1;
  15. bool vis[N];
  16. struct Edge{
  17.     int nxt,to,val;
  18. }ed[M];
  19. queue<int>q;
  21. int read(){
  22.     int x=0,f=1;char c=getchar();
  23.     while(c<'0' || c>'9') f=(c=='-')?-1:1,c=getchar();
  24.     while(c>='0' && c<='9') x=x*10+c-48,c=getchar();
  25.     return x*f;
  26. }
  28. void add(int u,int v,int w){
  29.     ed[++cnt]=(Edge){head[u],v,w};head[u]=cnt;
  30.     ed[++cnt]=(Edge){head[v],u,0};head[v]=cnt;
  31.     return;
  32. }
  34. bool bfs(){
  35.     while(!q.empty()) q.pop();
  36.     memset(d,0,sizeof(d));
  37.     d[s]=1;q.push(s);
  38.     while(!q.empty()){
  39.         int u=q.front();q.pop();
  40.         for(int i=head[u];i;i=ed[i].nxt){
  41.             int v=ed[i].to,w=ed[i].val;
  42.             if(w && !d[v]){
  43.                 d[v]=d[u]+1;
  44.                 if(v==t) return true;
  45.                 q.push(v);
  46.             }
  47.         }
  48.     }
  49.     return false;
  50. }
  52. int Dinic(int u,int flow){
  53.     if(u==t) return flow;
  54.     int rest=flow;
  55.     for(int i=head[u];i && rest;i=ed[i].nxt){
  56.         int v=ed[i].to,w=ed[i].val;
  57.         if(w && d[v]==d[u]+1){
  58.             int k=Dinic(v,min(w,rest));
  59.             if(!k) d[v]=0;
  60.             ed[i].val-=k;
  61.             ed[i^1].val+=k;
  62.             rest-=k;
  63.             pre[u>>1]=v>>1;
  64.             //开始建图时乘 2 了。
  65.             //很巧的是 (u<<1)>>1=(u<<1|1)>>1=u。 
  66.         }
  67.     }
  68.     return flow-rest;
  69. }
  71. int main(){
  72.     n=read();
  73.     int now=0,Pillar=0;
  74.     while(Pillar<=n){//如果柱子数 > n 就退出。
  75.         ++now;
  76.         add(s,now<<1,1);//和源点连接。
  77.         add(now<<1|1,t,1);//和汇点连接。
  78.         for(int i=sqrt(now)+1;i*i<(now<<1);i++)//和比自己小的能与自己组成完全平方数的数连边。
  79.             add((i*i-now)<<1,now<<1|1,1);//注意细节。
  80.         int flow,ans=0;
  81.         while(bfs())
  82.             if(flow=Dinic(s,INF)) ans+=flow;
  83.         if(!ans)//如果找不到增广路。
  84.             frs[++Pillar]=now;
  85.     }
  86.     printf("%d\n",--now);//记得减 1，因为最后的球肯定是放在第 n+1 个柱子上的。
  87.     memset(vis,false,sizeof(vis));
  88.     for(int i=1;i<=n;i++){
  89.         if(vis[frs[i]]) continue;//如果之前见过你了就不用输出了。
  90.         for(int u=frs[i];u && u!=(t>>1);u=pre[u])
  91.             vis[u]=true,printf("%d ",u);
  92.         puts("");
  93.     }
  94.     return 0;
  95. }

星际转移问题

  1. #include<cstdio>
  2. #include<cstring>
  3. #include<iostream>
  4. #include<cmath>
  5. #include<algorithm>
  6. #include<cstdlib>
  7. #define N 1000010
  8. #define M 2000010
  9. #define P 110
  10. #define s 0
  11. #define t N-10
  12. #define INF 0x3f3f3f3f
  13. using namespace std;
  15. int n,m,k,ans,head[N],cnt=1;
  16. int d[N];
  17. int r[P],g[P][P],h[P];
  18. int fa[P],q[N];
  19. struct Edge{
  20.     int nxt,to,val;
  21. }ed[M];
  23. int read(){
  24.     int x=0,f=1;char c=getchar();
  25.     while(c<'0' || c>'9') f=(c=='-')?-1:1,c=getchar();
  26.     while(c>='0' && c<='9') x=x*10+c-48,c=getchar();
  27.     return x*f; 
  28. }
  30. void init(){
  31.     n=read(),m=read(),k=read();
  32.     for(int i=1;i<=m;i++){
  33.         h[i]=read(),r[i]=read();
  34.         for(int j=0;j<r[i];j++) g[i][j]=read();
  35.     }
  36.     return;
  37. }
  39. int find(int x){
  40.     if(fa[x]==x) return x;
  41.     return fa[x]=find(fa[x]);
  42. }
  44. void merge(int x,int y){
  45.     int fx=find(x);
  46.     int fy=find(y);
  47.     if(fx!=fy) fa[fx]=fy;
  48.     return;
  49. }
  51. void pre_chck(){
  52.     for(int i=1;i<=n+2;i++) fa[i]=i;
  53.     for(int i=1;i<=m;i++)
  54.         for(int j=0;j<r[i];j++){
  55.             if(g[i][j]==0) g[i][j]=n+1;
  56.             if(g[i][j]==-1) g[i][j]=n+2; 
  57.             if(j!=0) merge(g[i][j],g[i][j-1]);
  58.         }
  59.     if(find(n+1)!=find(n+2)){puts("0");exit(0);}
  60.     return;
  61. }
  63. void add(int u,int v,int w){
  64.     ed[++cnt]=(Edge){head[u],v,w};head[u]=cnt;
  65.     ed[++cnt]=(Edge){head[v],u,0};head[v]=cnt;
  66.     return;
  67. }
  70. bool bfs(){
  71.     for(int i=1;i<=ans*(n+1);i++) d[i]=0;//千万别用 memset。
  72.     d[t]=0;
  73.     d[s]=1;q[1]=s;
  74.     int h=1,tail=1;
  75.     while(h<=tail){
  76.         int u=q[h];++h;
  77.         for(int i=head[u];i;i=ed[i].nxt){
  78.             int v=ed[i].to,w=ed[i].val;
  79.             if(w && !d[v]){
  80.                 d[v]=d[u]+1;
  81.                 if(v==t) return true;
  82.                 q[++tail]=v;
  83.             }
  84.         }
  85.     }
  86.     return false;
  87. }
  89. int Dinic(int u,int flow){
  90.     if(u==t) return flow;
  91.     int i,rest=0;
  92.     for(i=head[u];i;i=ed[i].nxt){
  93.         int v=ed[i].to,w=ed[i].val;
  94.         if(w && d[v]==d[u]+1){
  95.             int k=Dinic(v,min(flow-rest,w));
  96.             if(!k) d[v]=0;
  97.             ed[i].val-=k;
  98.             ed[i^1].val+=k;
  99.             rest+=k;
  100.             if(rest==flow) return rest;
  101.         }
  102.     }
  103.     return rest;
  104. }
  106. int main(){
  107.     init();
  108.     pre_chck();//并查集判无解。
  109.     int now=0;
  110.     for(ans=1;;ans++){
  111.         add(s,ans*(n+1),INF);
  112.         for(int i=1;i<=m;i++){
  113.             int x=(ans-1)%r[i],y=ans%r[i];
  114.             if(g[i][x]==n+2) x=t;
  115.             else x=(ans-1)*(n+1)+g[i][x];
  116.             if(g[i][y]==n+2) y=t;
  117.             else y=ans*(n+1)+g[i][y];
  118.             add(x,y,h[i]);
  119.         }//日常建边。
  120.         while(bfs()) now+=Dinic(s,INF);//利用残量网络跑 Dinic。
  121.         if(now>=k){printf("%d\n",ans);return 0;}
  122.         for(int i=1;i<=n+1;i++)
  123.             add((ans-1)*(n+1)+i,ans*(n+1)+i,INF);//向下一层转移。
  124.     }
  125.     return 0;
  126. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注