首页 > 代码库 > UVa 11248 网络扩容（最大流（需要优化））
UVa 11248 网络扩容（最大流（需要优化））
https://vjudge.net/problem/UVA-11248
题意：
给定一个有向网络，每条边均有一个容量。问是否存在一个从点1到点N，流量为C的流。如果不存在，是否可以恰好修改一条弧的容量，使得存在这样的流。
思路：
先求一遍最大流，如果大于等于C，那么就直接输出possible。
否则的话就是最大流达不到C，那么对哪些边进行扩容呢，肯定是选择最小割！
将最小割的边集全部求出来，之后每条边都尝试将容量变为C，看看能否达到要求。
优化一：求完最大流后把流量留着，以后每次在它的基础上增广。
优化二：每次没必要求出最大流，增广到流量至少为C时就可以停下来。
1 #include<iostream> 2 #include<algorithm> 3 #include<cstring> 4 #include<cstdio> 5 #include<vector> 6 #include<queue> 7 #include<cmath> 8 #include<map> 9 using namespace std; 10 11 const int maxn=100+5; 12 const int INF=0x3f3f3f3f; 13 14 struct Edge 15 { 16 int from,to,cap,flow; 17 Edge(int u,int v,int w,int f):from(u),to(v),cap(w),flow(f){} 18 }; 19 20 struct Dinic 21 { 22 int n,m,s,t; 23 vector<Edge> edges; 24 vector<int> G[maxn]; 25 bool vis[maxn]; 26 int cur[maxn]; 27 int d[maxn]; 28 29 void init(int n) 30 { 31 this->n=n; 32 for(int i=0;i<n;++i) G[i].clear(); 33 edges.clear(); 34 } 35 36 void AddEdge(int from,int to,int cap) 37 { 38 edges.push_back( Edge(from,to,cap,0) ); 39 edges.push_back( Edge(to,from,0,0) ); 40 m=edges.size(); 41 G[from].push_back(m-2); 42 G[to].push_back(m-1); 43 } 44 45 bool BFS() 46 { 47 queue<int> Q; 48 memset(vis,0,sizeof(vis)); 49 vis[s]=true; 50 d[s]=0; 51 Q.push(s); 52 while(!Q.empty()) 53 { 54 int x=Q.front(); Q.pop(); 55 for(int i=0;i<G[x].size();++i) 56 { 57 Edge& e=edges[G[x][i]]; 58 if(!vis[e.to] && e.cap>e.flow) 59 { 60 vis[e.to]=true; 61 d[e.to]=d[x]+1; 62 Q.push(e.to); 63 } 64 } 65 } 66 return vis[t]; 67 } 68 69 int DFS(int x,int a) 70 { 71 if(x==t || a==0) return a; 72 int flow=0, f; 73 for(int &i=cur[x];i<G[x].size();++i) 74 { 75 Edge &e=edges[G[x][i]]; 76 if(d[e.to]==d[x]+1 && (f=DFS(e.to,min(a,e.cap-e.flow) ) )>0) 77 { 78 e.flow +=f; 79 edges[G[x][i]^1].flow -=f; 80 flow +=f; 81 a -=f; 82 if(a==0) break; 83 } 84 } 85 return flow; 86 } 87 88 int Maxflow(int s,int t,int need) 89 { 90 this->s=s; this->t=t; 91 int flow=0; 92 while(BFS()) 93 { 94 memset(cur,0,sizeof(cur)); 95 flow +=DFS(s,INF); 96 if(flow>=need) return flow; 97 } 98 return flow; 99 }100 101 //最小割的边集102 vector<int> Mincut()103 {104 BFS();105 vector<int> ans;106 for(int i=0;i<edges.size();i++)107 {108 Edge& e=edges[i];109 if(vis[e.from] && !vis[e.to] && e.cap>0) ans.push_back(i);110 }111 return ans;112 }113 114 void Reduce()115 {116 for(int i=0;i<edges.size();i++)117 {118 Edge& e=edges[i];119 e.cap-=e.flow;120 }121 }122 123 void Clearflow()124 {125 for(int i=0;i<edges.size();i++)126 {127 Edge& e=edges[i];128 e.flow=0;129 }130 };131 132 }DC;133 134 int n,e,c;135 136 bool cmp(Edge a,Edge b)137 {138 return a.from<b.from||((a.from==b.from)&&(a.to<b.to));139 }140 141 int main()142 {143 //freopen("D:\\input.txt","r",stdin);144 int kase=0;145 while(~scanf("%d%d%d",&n,&e,&c))146 {147 if(!n) break;148 DC.init(n+1);149 int u,v,w;150 for(int i=0;i<e;i++)151 {152 scanf("%d%d%d",&u,&v,&w);153 DC.AddEdge(u,v,w);154 }155 printf("Case %d: ",++kase);156 int ans=DC.Maxflow(1,n,INF);157 if(ans>=c)158 {159 printf("possible\n");160 continue;161 }162 vector<int> cut=DC.Mincut();163 DC.Reduce();164 vector<Edge> change;165 for(int i=0;i<cut.size();i++)166 {167 DC.Clearflow();168 Edge& e=DC.edges[cut[i]];169 int temp=e.cap;170 e.cap=c;171 if(DC.Maxflow(1,n,c-ans)>=c-ans) change.push_back(e);172 e.cap=temp;173 }174 if(change.empty())175 {176 printf("not possible\n");177 continue;178 }179 sort(change.begin(),change.end(),cmp);180 printf("possible option:");181 printf("(%d,%d)",change[0].from,change[0].to);182 for(int i=1;i<change.size();i++)183 printf(",(%d,%d)",change[i].from,change[i].to);184 printf("\n");185 }186 }
UVa 11248 网络扩容（最大流（需要优化））
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。