首页 > 代码库 > 【网络流#5】UVA 11082 最大流
【网络流#5】UVA 11082 最大流
网络流题目最有意思的地方就是构图了，毕竟套模板每个人都会的
现在有一个矩阵，已知前i行元素之和a[i]（1<=i<=n），前j列元素之和b[j]（1<=j<=m），求一个可行的矩阵，且矩阵每个元素在区间[1,20]内。
这也算是含上下界的网络流了，但是显然，如果将每个元素都减一，就是普通的最大流了，矩阵元素值在区间[0,19]内。
首先求出第i行元素之和r[i]，第j列元素之和c[j]，
然后就是建图，每行化为一个结点1~n，每列化为一个结点n+1~n+m
源点到1~n，分别连一条边，容量为r[i]-m
n+1~n+m到汇点，分别连一条边，容量为c[i]-n
1~n到n+1~n+m，分别连一条容量为19的边
这样跑一发网络流
1 #include<cstdio> 2 #include<cstring> 3 #include<cmath> 4 #include<iostream> 5 #include<algorithm> 6 #include<set> 7 #include<map> 8 #include<stack> 9 #include<vector> 10 #include<queue> 11 #include<string> 12 #include<sstream> 13 #define MAXN 1000 14 #define MAXM 2000 15 #define INF (1<<30) 16 #define eps 0.000001 17 #define ALL(x) x.begin(),x.end() 18 #define INS(x) inserter(x,x.begin()) 19 using namespace std; 20 const int inf = 0x3f3f3f3f; 21 int i,j,k,n,m,x,y,T,num,w,cas,s,t,maxflow,u; 22 struct edgenode 23 { 24 int from,to,next; 25 int cap; 26 }edge[MAXM]; 27 int Edge,head[MAXN],ps[MAXN],dep[MAXN],r[MAXN],c[MAXN],tt; 28 int ans[MAXN][MAXN]; 29 30 void add_edge(int x,int y,int c) 31 { 32 edge[Edge].from=x; 33 edge[Edge].to=y; 34 edge[Edge].cap=c; 35 edge[Edge].next=head[x]; 36 head[x]=Edge++; 37 38 edge[Edge].from=y; 39 edge[Edge].to=x; 40 edge[Edge].cap=0; 41 edge[Edge].next=head[y]; 42 head[y]=Edge++; 43 } 44 /*关于这个模板： 45 Edge为前向星的边数，所以需要初始化Edge和head数组 46 n表示有n个点，这个版无所谓点从0开始还是从1开始，s表示源点，t表示汇点 47 很好的一个是，这个版的DFS使用的是模拟栈，防止爆栈 48 */ 49 50 int dinic(int n,int s,int t) 51 { 52 int tr,res=0; 53 int i,j,k,l,r,top; 54 while(1){ 55 memset(dep,-1,(n+1)*sizeof(int)); 56 for(l=dep[ps[0]=s]=0,r=1;l!=r;)//BFS部分，将给定图分层 57 { 58 for(i=ps[l++],j=head[i];j!=-1;j=edge[j].next) 59 { 60 if (edge[j].cap&&-1==dep[k=edge[j].to]) 61 { 62 dep[k]=dep[i]+1;ps[r++]=k; 63 if(k==t) 64 { 65 l=r; 66 break; 67 } 68 } 69 } 70 } 71 if(dep[t]==-1)break; 72 73 for(i=s,top=0;;)//DFS部分 74 { 75 if(i==t)//当前点就是汇点时 76 { 77 for(k=0,tr=inf;k<top;++k) 78 if(edge[ps[k]].cap<tr)tr=edge[ps[l=k]].cap; 79 80 for(k=0;k<top;++k) 81 edge[ps[k]].cap-=tr,edge[ps[k]^1].cap+=tr; 82 83 res+=tr; 84 i=edge[ps[top=l]].from; 85 } 86 87 for(j=head[i];j!=-1;j=edge[j].next)//找当前点所指向的点 88 if(edge[j].cap&&dep[i]+1==dep[edge[j].to]) break; 89 90 if(j!=-1) 91 { 92 ps[top++]=j;//当前点有所指向的点，把这个点加入栈中 93 i=edge[j].to; 94 } 95 else 96 { 97 if (!top) break;//当前点没有指向的点，回溯 98 dep[i]=-1; 99 i=edge[ps[--top]].from;100 }101 }102 }103 return res;104 }105 106 int main()107 {108 scanf("%d",&T);109 for (cas=1;cas<=T;cas++)110 { 111 memset(head,-1,sizeof(head));112 Edge=0;113 114 scanf("%d%d",&n,&m);115 int pre=0;116 for (i=1;i<=n;i++)117 {118 scanf("%d",&r[i]);119 add_edge(0,i,r[i]-m-pre);120 pre=r[i];121 }122 tt=n+m+1; 123 pre=0;124 for (i=1;i<=m;i++)125 {126 scanf("%d",&c[i]);127 add_edge(i+n,tt,c[i]-n-pre);128 pre=c[i];129 }130 for (i=1;i<=n;i++)131 {132 for (j=1;j<=m;j++)133 {134 add_edge(i,n+j,19);135 }136 }137 138 maxflow=dinic(tt+1,0,tt);139 //cout<<maxflow<<endl;140 for (i=1;i<=n;i++)141 {142 for (j=head[i];j!=-1;j=edge[j].next)143 {144 u=edge[j].to;145 if (u<=n||u>n+m) continue;146 ans[i][u-n]=19-edge[j].cap;147 }148 }149 printf("Matrix %d\n",cas);150 for (i=1;i<=n;i++)151 {152 for (j=1;j<m;j++)153 {154 printf("%d ",ans[i][j]+1);155 }156 printf("%d\n",ans[i][m]+1);157 }158 if (cas!=T) printf("\n");159 }160 return 0;161 }
至于真正含上下界的问题，还要参考霓虹的那本书
【网络流#5】UVA 11082 最大流
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。