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;
}