題目：城市間有若干條道路，士兵可以經過道路到相鄰的城市，現在給定初始每個城鎮的士兵數目和最終的數目，問是否可以達到最終局面。

思路：關鍵是建圖，首先從源點到初始城鎮連邊，然后把有邊的初始城鎮和結束城鎮連邊，最后把結束城鎮和匯點連邊，這樣就可以保證題目中的“每個士兵最多經過一條道路”的條件，然后求出最大流，如果與城鎮總人數相等，那么就有解。輸出解的時候只需要把反向邊的流量輸出即可。

#include<iostream> #include<map> #include<algorithm> #include<cstdio> #include<cstring> #include<cstdlib> #include<vector> #include<queue> #include<stack> #include<functional> #include<set> #include<cmath> #define pb push_back #define fs first #define se second #define sq(x) (x)*(x) #define eps 0.0000000001 #define IINF (1<<30) using namespace std; typedef long long ll; typedef pair<ll,ll> P; const int maxv=105*4; struct EDGE{int to,cap,rev;EDGE(int t,int c,int r){to=t,cap=c,rev=r;} }; vector<EDGE> G[maxv]; void addedge(int f,int t,int c){G[f].pb(EDGE(t,c,G[t].size()));G[t].pb(EDGE(f,0,G[f].size()-1)); } int level[maxv],iter[maxv]; queue<int> Q; void bfs(int s){memset(level,-1,sizeof level);level[s]=0;Q.push(s);while(!Q.empty()){int v=Q.front();Q.pop();for(int i=0;i<G[v].size();i++){EDGE &e=G[v][i];if(e.cap>0&&level[e.to]<0){level[e.to]=level[v]+1;Q.push(e.to);}}} } int dfs(int v,int t,int f){if(v==t) return f;for(int &i=iter[v];i<G[v].size();i++){EDGE &e=G[v][i];if(e.cap>0&&level[v]<level[e.to]){int d=dfs(e.to,t,min(f,e.cap));if(d>0){e.cap-=d;G[e.to][e.rev].cap+=d;return d;}}}return 0; } int dinic(int s,int t){int flow=0;while(1){bfs(s);if(level[t]<0) return flow;memset(iter,0,sizeof iter);int f;while((f=dfs(s,t,IINF))>0){flow+=f;}} } int a[maxv],b[maxv]; int n,m; int s=maxv-3,t=maxv-4; int sa=0,sb=0; int out[maxv][maxv]; int main(){freopen("/home/files/CppFiles/in","r",stdin);/* std::ios::sync_with_stdio(false);std::cin.tie(0);*/cin>>n>>m;for(int i=1;i<=n;i++){scanf("%d",a+i);addedge(s,i,a[i]);addedge(i,i+n,IINF);sa+=a[i];}for(int i=1;i<=n;i++){scanf("%d",b+i);addedge(i+n,t,b[i]);sb+=b[i];}for(int i=0;i<m;i++){int p,q;scanf("%d%d",&p,&q);addedge(p,q+n,IINF);addedge(q,p+n,IINF);}int ans=dinic(s,t);for(int i=1;i<=n;i++){for(int j=0;j<G[i].size();j++){EDGE &e=G[i][j];if(e.to-n>n) continue;EDGE &r=G[e.to][e.rev];out[i][e.to-n]=r.cap;}}if(ans==sa&&sa==sb){cout<<"YES"<<endl;for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){cout<<out[i][j]<<" ";}cout<<endl;}}else{cout<<"NO"<<endl;}return 0; } View Code

?

轉載于:https://www.cnblogs.com/Cw-trip/p/4685945.html

總結

以上是生活随笔為你收集整理的CF 546E(最大流的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。