最大流（拆点）总结

本文主要是介绍最大流（拆点）总结，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

51nod1442

思路，拆点，一个点拆成入点和出点，再建一个超级汇点和超级源点。源点和入点相连，cap为每个点对应的初始士兵人数，出点和汇点相连，cap为移动后每个城市的士兵数。其它点之间cap为无穷大（这里无穷大是指可以任意流），需要注意的是一个点和另一个点连接，是这个点的入点和下一个出点相连而不是连去下一个点的入点，这样可以保证每个士兵只可以到相邻。最后跑一次最大流，统计最大流是否和初始人数相等。（为什么可以最大流？因为进入一个点是士兵原来的数，出去是移动后的兵人数，也就是说二者的差额即被移动的人数在各个点之间流动，达到平衡）

#include<cstring>
#include<cstdio>
#include<vector>
#include<queue>
#include<iostream>
#include<algorithm>
#define inf 0x3f3f3f3f
#define debug cout<<"debug"<<endl;
using namespace std;
const int maxn=1e4+50;
int n,m,u,v,sum1,sum2,ans,a[maxn],p[maxn],s,t;struct Edge{int from,to,cap,flow;Edge(int fr,int tt,int cc,int fl):from(fr),to(tt),cap(cc),flow(fl){}
};
vector<Edge> e;
vector<int> g[maxn];void max_flow(int s,int t){ans=0;for(;;){//debugmemset(a,0,sizeof(a));a[s]=inf;queue<int> q;q.push(s);while(!q.empty()){int temp=q.front();q.pop();for(int i=0;i<g[temp].size();i++){Edge &edge=e[g[temp][i]];if(!a[edge.to]&&edge.cap>edge.flow){a[edge.to]=min(a[temp],edge.cap-edge.flow);p[edge.to]=g[temp][i];q.push(edge.to);}}if(a[t]) break;}		if(!a[t]) break;for(int i=t;i!=s;i=e[p[i]].from){e[p[i]].flow+=a[t];e[p[i]^1].flow-=a[t];}ans+=a[t];}
}int main(){while(scanf("%d%d",&n,&m)!=EOF){s=sum1=sum2=ans=0;t=(n<<1)+1;memset(g,0,sizeof(g));memset(p,0,sizeof(p));e.clear();for(int i=1;i<=n;i++){int temp;scanf("%d",&temp);sum1+=temp;e.push_back(Edge(s,i,temp,0));g[s].push_back(e.size()-1);///连去起点不需要双向存图 e.push_back(Edge(i,s,0,0));g[i].push_back(e.size()-1);e.push_back(Edge(i,i+n,inf,0));g[i].push_back(e.size()-1);e.push_back(Edge(i+n,i,0,0));g[i+n].push_back(e.size()-1); }for(int i=1;i<=n;i++){int temp;scanf("%d",&temp);sum2+=temp;e.push_back(Edge(i+n,t,temp,0));g[i+n].push_back(e.size()-1);e.push_back(Edge(t,i,0,0));g[t].push_back(e.size()-1);}for(int i=1;i<=m;i++){scanf("%d%d",&u,&v);e.push_back(Edge(u,v+n,inf,0));g[u].push_back(e.size()-1);e.push_back(Edge(v+n,u,0,0));g[v+n].push_back(e.size()-1); e.push_back(Edge(v,u+n,inf,0));g[v].push_back(e.size()-1);e.push_back(Edge(u+n,v,0,0));g[u+n].push_back(e.size()-1);}max_flow(s,t);if(ans==sum1&&sum1==sum2) printf("YES\n");else printf("NO\n");}	return 0;
}

uva563

这题就是《算导》最大流课后的第一道题。

思路：因为这道题点和边都有限流，所以把每个点拆点，拆分后两点间连cap==1,这样可以保证每个点只能流过一个人，然后其他点之间的边连cap==1，跑一遍最大流，统计人数是否相等。

#include<cstdio>
#include<iostream>
#include<cstring>
#include<queue>
#include<vector> 
#include<algorithm>
#define inf 0x3f3f3f3f
#define debug cout<<"debug"<<endl; 
const int maxn=1e6+50;
using namespace std;
int p,street,avenue,bank,a[maxn],pa[maxn],x,y,s,t,ans;struct Edge{int from,to,cap,flow;Edge(int fr,int tt,int ca,int fl):from(fr),to(tt),cap(ca),flow(fl){} 
};
vector<int> g[maxn];
vector<Edge> e;int getid(int x,int y){return (x-1)*avenue+y;
}bool is_Bound(int x,int y){if(x>1&&x<street&&y>1&&y<avenue) return false;return true;
}void init_graph(){for(int i=1;i<=street;i++)for(int j=1;j<=avenue;j++){int id=getid(i,j); ///u u'建边 e.push_back(Edge(id,id+street*avenue,1,0));g[id].push_back(e.size()-1);e.push_back(Edge(id+street*avenue,id,0,0));g[id+street*avenue].push_back(e.size()-1);///与四周建边 if(!is_Bound(i,j)){e.push_back(Edge(id+street*avenue,id+avenue,1,0));///down g[id+street*avenue].push_back(e.size()-1);e.push_back(Edge(id+avenue,id+street*avenue,0,0));g[id+avenue].push_back(e.size()-1);e.push_back(Edge(id+street*avenue,id-avenue,1,0));g[id+street*avenue].push_back(e.size()-1);e.push_back(Edge(id-street,id+street*avenue,0,0));g[id-avenue].push_back(e.size()-1);///upe.push_back(Edge(id+street*avenue,id+1,1,0));g[id+street*avenue].push_back(e.size()-1);e.push_back(Edge(id+1,id+street*avenue,0,0));g[id+1].push_back(e.size()-1);///righte.push_back(Edge(id+street*avenue,id-1,1,0));g[id+street*avenue].push_back(e.size()-1);e.push_back(Edge(id-1,id+street*avenue,0,0));g[id-1].push_back(e.size()-1);///left}else{if(i==street){e.push_back(Edge(id+street*avenue,id-avenue,1,0));g[id+street*avenue].push_back(e.size()-1);e.push_back(Edge(id-street,id+street*avenue,0,0));g[id-avenue].push_back(e.size()-1);///upe.push_back(Edge(id+street*avenue,id+1,1,0));g[id+street*avenue].push_back(e.size()-1);e.push_back(Edge(id+1,id+street*avenue,0,0));g[id+1].push_back(e.size()-1);///righte.push_back(Edge(id+street*avenue,id-1,1,0));g[id+street*avenue].push_back(e.size()-1);e.push_back(Edge(id-1,id+street*avenue,0,0));g[id-1].push_back(e.size()-1);///left}else if(i==1){e.push_back(Edge(id+street*avenue,id+avenue,1,0));///down g[id+street*avenue].push_back(e.size()-1);e.push_back(Edge(id+avenue,id+street*avenue,0,0));g[id+avenue].push_back(e.size()-1);e.push_back(Edge(id+street*avenue,id+1,1,0));g[id+street*avenue].push_back(e.size()-1);e.push_back(Edge(id+1,id+street*avenue,0,0));g[id+1].push_back(e.size()-1);///righte.push_back(Edge(id+street*avenue,id-1,1,0));g[id+street*avenue].push_back(e.size()-1);e.push_back(Edge(id-1,id+street*avenue,0,0));g[id-1].push_back(e.size()-1);///left}else if(j==1){e.push_back(Edge(id+street*avenue,id+avenue,1,0));///down g[id+street*avenue].push_back(e.size()-1);e.push_back(Edge(id+avenue,id+street*avenue,0,0));g[id+avenue].push_back(e.size()-1);e.push_back(Edge(id+street*avenue,id-avenue,1,0));g[id+street*avenue].push_back(e.size()-1);e.push_back(Edge(id-street,id+street*avenue,0,0));g[id-avenue].push_back(e.size()-1);///upe.push_back(Edge(id+street*avenue,id+1,1,0));g[id+street*avenue].push_back(e.size()-1);e.push_back(Edge(id+1,id+street*avenue,0,0));g[id+1].push_back(e.size()-1);///right}else if(j==avenue){e.push_back(Edge(id+street*avenue,id+avenue,1,0));///down g[id+street*avenue].push_back(e.size()-1);e.push_back(Edge(id+avenue,id+street*avenue,0,0));g[id+avenue].push_back(e.size()-1);e.push_back(Edge(id+street*avenue,id-avenue,1,0));g[id+street*avenue].push_back(e.size()-1);e.push_back(Edge(id-street,id+street*avenue,0,0));g[id-avenue].push_back(e.size()-1);///upe.push_back(Edge(id+street*avenue,id-1,1,0));g[id+street*avenue].push_back(e.size()-1);e.push_back(Edge(id-1,id+street*avenue,0,0));g[id-1].push_back(e.size()-1);///left}e.push_back(Edge(id+street*avenue,t,1,0));g[id+street*avenue].push_back(e.size()-1);e.push_back(Edge(t,id+street*avenue,0,0));g[t].push_back(e.size()-1); }	}
}void max_flow(int s,int t){ans=0;for(;;){memset(a,0,sizeof(a));a[s]=inf; queue<int> q;q.push(s);while(!q.empty()){int temp=q.front();q.pop();for(int i=0;i<g[temp].size();i++){Edge &edge=e[g[temp][i]];if(!a[edge.to]&&edge.cap>edge.flow){a[edge.to]=min(a[temp],edge.cap-edge.flow);pa[edge.to]=g[temp][i];q.push(edge.to);	}}if(a[t]) break;}if(!a[t]) break;for(int i=t;i!=s;i=e[pa[i]].from){e[pa[i]].flow+=a[t];e[pa[i]^1].flow-=a[t];}ans+=a[t];}
}int main(){//freopen("out.txt","w",stdout);while(scanf("%d",&p)!=EOF){for(int cas=1;cas<=p;cas++){e.clear();memset(g,0,sizeof(g));memset(pa,0,sizeof(pa));scanf("%d%d%d",&street,&avenue,&bank);s=0;t=(street*avenue)<<1+1;init_graph();for(int i=1;i<=bank;i++){scanf("%d%d",&x,&y);int id=getid(x,y);e.push_back(Edge(s,id,1,0));g[s].push_back(e.size()-1);e.push_back(Edge(id,s,0,0));g[id].push_back(e.size()-1);}max_flow(s,t);if(ans==bank) printf("possible\n");else printf("not possible\n");}}return 0;
}

这篇关于最大流（拆点）总结的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！