Codeforces Round #304 (Div. 2) E Soldier and Traveling
sourceとsinkを追加し流量制限にa[i],b[i]を与えることで二部グラフのフローになることは本番中に気づいたが、YESだった場合に経路復元する方法が分からなかった。
考えてみると、逆辺のcapはその辺に流したフローの量であるから、ここから容易に復元することができる。
それと、source=2n, sink=2n+1 みたいに置いておくと、デバッグしやすいことを教えてもらった。
#include <bits/stdc++.h> using namespace std; #define REP(i,n) for(int i=0;i<(int)(n);i++) //Ford-Fulkerson's algorithm struct edge{int to,cap,rev;}; const int INF=1e9; void addEdge(vector<vector<edge> > &g,int from,int to,int cap){ g[from].push_back((edge){to,cap,(int)g[to].size()}); g[to].push_back((edge){from,0,(int)g[from].size()-1}); } int dfs(vector<vector<edge> > &g,vector<bool> &used,int v,int t,int f){ if(v==t) return f; used[v]=true; for(int i=0;i<(int)g[v].size();i++){ edge& e=g[v][i]; if(!used[e.to] && e.cap>0){ int d=dfs(g,used,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 FordFulkerson(vector<vector<edge> > &g,int s,int t){ int flow=0; for(;;){ vector<bool> used(g.size(),false); int f=dfs(g,used,s,t,INF); if(f==0) return flow; flow+=f; } } // int main(){ int n,m; cin >> n >> m; vector<int> a(n),b(n); REP(i,n) cin >> a[i]; REP(i,n) cin >> b[i]; vector<vector<edge> > g(2*n+2); int source=2*n; int sink=2*n+1; REP(i,n) addEdge(g,source,i,a[i]); REP(i,n) addEdge(g,n+i,sink,b[i]); REP(i,n) addEdge(g,i,n+i,INF); REP(i,m){ int p,q; cin >> p >> q; addEdge(g,p-1,q-1+n,INF); addEdge(g,q-1,p-1+n,INF); } int sum1=0,sum2=0; REP(i,n){ sum1+=a[i]; sum2+=b[i]; } int f=FordFulkerson(g,source,sink); if(f!=max(sum1,sum2)){ cout << "NO" << endl; }else{ vector<vector<int> > res(n,vector<int> (n)); REP(i,n){ for(auto e : g[i+n]){ if(e.to<n) res[e.to][i]=e.cap; } } cout << "YES" << endl; REP(i,n){ REP(j,n){ if(j) cout << " "; cout << res[i][j]; } cout << endl; } } return 0; }