首页 > 代码库 > 有上下界的网络流3-有源汇带上下界最小流SGU176
有上下界的网络流3-有源汇带上下界最小流SGU176
题目大意：有一个类似于工业加工生产的机器，起点为1终点为n，中间生产环节有货物加工数量限制，输入u v z c， 当c等于1时表示这个加工的环节必须对纽带上的货物全部加工（即上下界都为z），c等于0表示加工上界限制为z，下界为0，求节点1（起点）最少需要投放多少货物才能传送带正常工作。
解题思路：
1.直接 增设超级源点ss和超级汇点tt并连上附加边，对 当前图 求 无源汇带上下界可行流
2.将图的汇点sd连一条容量无限制的边到图的源点st，再求一遍 无源汇带上下界可行流
3.如果当前求得的可行流中所有附加边（与超级源点ss和超级汇点tt相连的边）的流量为满，则存在可行的流量符合题目要求，并且当前图中的流量 即为可行的最小流。如果附加边流量未满则不存在可行流。
为什么要求两遍无源汇带上下界可行流？直接连一条边从汇点sd到源点st，并将这条边流量设为无穷大，再求无源汇带上下界可行流不就是需要求的有源汇带上下界最小流吗？最小流不就是满足流量限制的可行流吗？
-----------可是事实并不是这样的。。
对于这样的图，如果我们直接将汇点连向源点并将这条边的流量限制置为正无穷，求出的最小流量为200。而实际上我们可以这样走S->1->3->2->1->3->2->T，只需要100的流量即可满足要求。所以我们要求得可行的最小流，必须先不连接汇点和源点求一次无源汇带上下界的可行流，再将汇点和源点连上，再求无源汇带上下界的可行流（这样做的原理是使超级源点ss发出的流量尽量别走汇点sd到源点st那条边，先走其他能走的边，这样才能达到汇点到源点那条边的流量最小），此时汇点到源点的那条边的流量即为所求的最小可行流。
附个代码：
1 #include<iostream> 2 #include<cstdio> 3 #include<cstdlib> 4 #include<algorithm> 5 #include<cstring> 6 #include<vector> 7 #include<queue> 8 #define maxn 0x7fffffff 9 using namespace std; 10 int n,m,st,sd,ss,tt; 11 struct edge{int to,cap,rev,num;}; 12 vector <edge> E[200]; 13 int ch[200],du[200],edge_flow[40100]; 14 bool bfs(int S,int T){ 15 memset(ch,-1,sizeof(ch)); 16 queue <int> que; 17 que.push(S);ch[S]=0; 18 while(que.size()){ 19 int t=que.front();que.pop(); 20 for(int i=0;i<E[t].size();i++){ 21 if(ch[E[t][i].to]==-1 && E[t][i].cap){ 22 ch[E[t][i].to]=ch[t]+1; 23 que.push(E[t][i].to); 24 } 25 } 26 } 27 return ch[T]>=0; 28 } 29 int dfs(int v,int T,int f){ 30 if(v==T) return f; 31 int r=0; 32 for(int i=0;i<E[v].size();i++){ 33 if(f==0) return r; 34 edge &t=E[v][i]; 35 if(ch[t.to]==ch[v]+1){ 36 int u=dfs(t.to,T,min(f,t.cap)); 37 t.cap-=u,E[t.to][t.rev].cap+=u; 38 f-=u,r+=u; 39 } 40 } 41 return r; 42 } 43 int dinic(int S,int T){ 44 int f=0; 45 while(bfs(S,T)) f+=dfs(S,T,maxn); 46 return f; 47 } 48 void Add_Edge(int from,int to,int low,int up,int num){ 49 edge t; 50 t.num=0; 51 t.to=to,t.cap=up-low,t.rev=E[to].size(); 52 E[from].push_back(t); 53 54 t.num=num; 55 t.to=from,t.cap=0,t.rev=E[from].size()-1; 56 E[to].push_back(t); 57 du[from]-=low,du[to]+=low; 58 } 59 void init(){ 60 int u,v,z,c; 61 scanf("%d%d",&n,&m); 62 st=1,sd=n,ss=0,tt=n+1; 63 for(int i=1;i<=m;i++){ 64 scanf("%d%d%d%d",&u,&v,&z,&c); 65 if(c){ 66 Add_Edge(u,v,z,z,i); 67 edge_flow[i]+=z; 68 } 69 else Add_Edge(u,v,0,z,i); 70 } 71 } 72 bool work(){ 73 int s=0; 74 for(int i=st;i<=sd;i++){ 75 if(du[i]>0){ 76 Add_Edge(ss,i,0,du[i],0); 77 s+=du[i]; 78 } 79 if(du[i]<0) Add_Edge(i,tt,0,-du[i],0); 80 } 81 s-=dinic(ss,tt); 82 Add_Edge(sd,st,0,maxn,0); 83 s-=dinic(ss,tt); 84 return s==0; 85 } 86 int main(){ 87 init(); 88 if(work()){ 89 for(int i=0;i<E[st].size();i++) 90 if(E[st][i].to==sd) printf("%d\n",E[st][i].cap); 91 for(int i=st;i<=sd;i++){ 92 for(int j=0;j<E[i].size();j++){ 93 if(E[i][j].num) edge_flow[E[i][j].num]+=E[i][j].cap; 94 } 95 } 96 for(int i=1;i<m;i++) printf("%d ",edge_flow[i]); 97 printf("%d\n",edge_flow[m]); 98 } 99 else{ 100 printf("Impossible\n"); 101 } 102 return 0; 103 }
有上下界的网络流3-有源汇带上下界最小流SGU176
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。