Codeforces Round #304 (Div. 2) E. Soldier and Traveling

問題

頂点 辺の無向が与えられる。最初、 番目の頂点には 人の兵士がおり、各兵士は隣接する頂点に移動するかその場にとどまるかを行う。ただし、兵士が移動できる辺の本数は1本までとする。

すべての移動後、 番目の頂点にいる兵士の人数を となるようにできるか判定せよ。可能である場合、その移動の方法を出力せよ。

問題リンク：Codeforces Round #304 (Div. 2) E. Soldier and Traveling

制約

• 
• 
• 

解法

では不可能なので とします。

問題を次のように読み替えます。「 番目の頂点への入力を、出力を となるようにネットワークを構築できるか？」このようにするとフローによって問題を解くことができます。

辺を1度までしか使えないという制約のため、頂点を入力側と出力側に分けます。入力側から出力側へ隣接する頂点間と自分自身に辺を張ることで辺を1度までしか使用しないようにします。辺の容量は十分大きな値とします。

始点と終点を用意し、始点から入力点へ容量 の辺、出力点から終点へ の辺を張ります。このとき始点から終点への最大流 が となっていれば構築可能です。

頂点間の流量は逆辺の容量からわかります。

Code

#include <bits/stdc++.h>
using namespace std;
 
constexpr int IINF = INT_MAX;
 
struct edge{
    int to, cap, rev;
    bool isrev;
};
 
vector<vector<edge> > G;
vector<bool> used;
 
void add_edge(int from, int to, int cap){
    G[from].emplace_back((edge){to, cap, int(G[to].size()), false});
    G[to].emplace_back((edge){from, 0, int(G[from].size())-1, true});
}
 
// 増加路の探索
int dfs(int v, int t, int f){
    if(v == t) return f;
    used[v] = true;
    for(auto &e : G[v]){
        if(!used[e.to] && e.cap > 0){
            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 max_flow(int s, int t){
    used.resize(G.size());
    int flow = 0;
    while(1){
        fill(used.begin(), used.end(), false);
        int f = dfs(s, t, IINF);
        if(f==0) break;
        flow += f;
    }
    return flow;
}
 
int main() {
    int n, m, asum = 0, bsum = 0;
    cin >> n >> m;
    G.resize(n*2+2);  // 入力点、出力点、始点、終点
    for(int i=0;i<n;i++){
        int a;
        cin >> a;
        add_edge(n*2, i, a);  // 始点->入力点
        asum += a;
    }
    for(int i=0;i<n;i++){
        int b;
        cin >> b;
        add_edge(i+n, n*2+1, b);  // 出力点->終点
        bsum += b;
    }
    for(int i=0;i<n;i++){
        add_edge(i, i+n, IINF);  // とどまる辺
    }
    for(int i=0;i<m;i++){
        int p, q;
        cin >> p >> q;
        p--; q--;
        add_edge(p, q+n, IINF);  // 隣接する頂点間の辺
        add_edge(q, p+n, IINF);
    }
    if(asum != bsum || max_flow(n*2, n*2+1) != asum){
        cout << "NO" << endl;
    }
    else{
        cout << "YES" << endl;
        vector<vector<int> > ans(n, vector<int>(n,0));
        for(int i=0;i<n;i++){
            for(auto &e : G[i+n]){
                if(e.isrev){
                    ans[e.to][i] += e.cap;
                }
            }
        }
        // 出力
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                cout << ans[i][j] << " \n"[j==n-1];
            }
        }
    }
    return 0;
}