Codeforces 546E - Soldier and Travelling

Problem Statement:
546E - Soldier and Travelling

Solution:
Firstly notice that we can think of the problem as an instance of linear programming. For each city i, let x[i][j] be the number of soldiers that move from city i to city j (in particular, x[i][i] is the number of soldiers that stay in the city).



From the problem statement, the first constraint that we have is a[i] = sum of x[i][j] from j = 1 to n (sum of all outgoing soldiers).
Furthermore, each city in the end must have exactly b[i] soldiers, hence we have our second constraint b[i] = sum of x[j][i] for j = 1 to n (sum of all incoming soldiers).

This instance of linear programming can be transformed into a maximum flow problem with directed edges. Let S be the source of the maxflow graph, and T be the sink. Next, we create 2n nodes as follows: for each city i, we create two nodes A[i] and B[i].

First we draw an edge with capacity a[i] from S to A[i], for all i = 1 to n. Then from each A[i], we draw an edge with infinite capacity to another node B[j] if there is a node from city i to city j (this relationship is bidirectional, hence we need to draw an edge from A[j] to B[i] as well for each pair of cities i and j). Finally draw an edge with capacity from B[i] to T with capacity b[i].

Now by running a maxflow algorithm, we can find the maximum flow from S to T. If the maximum flow is exactly equal to the sum of a[i] (or sum of b[i], since the sum should be equal), then the residual maxflow graph represents the value for all x[i][j]. Otherwise, there is no solution to the linear programming instance.

#include <iostream>
#include <cstdio>
#include <queue>
#include <vector>
#include <utility>
using namespace std;

int cap[300][300];
int flow[300][300];
vector<vector<int> > adj;
int s, t;
const int inf = 12345678;
int n;
int vis[300];
int par[300];

int pushflow(int v, int mf) {
    if(v == s) {
        return mf;
    }
    int u = par[v];
    if(cap[u][v]<=0) {
        mf = min(mf, flow[v][u]);
    } else {
        mf = min(mf, cap[u][v] - flow[u][v]);
    }
    mf = pushflow(u, mf);
    if(cap[u][v]<=0){
        flow[v][u] -= mf;
    } else {
        flow[u][v] += mf;
    }
    return mf;
}

int bfs() {
    int maxflow = 0;
    while(1){
        for(int i=0;i<2*n;++i) vis[i] = 0;
        vis[t] = 0;
        queue<int> q;
        q.push(s);
        vis[s] = 1;
        par[s] = -1;
        bool pushed = false;
        while(!q.empty()){
            int cur = q.front();
            q.pop();
            for(int i = 0;i < adj[cur].size();++i){
                int next = adj[cur][i];
                if(vis[next]) continue; 
                if(cap[cur][next] - flow[cur][next] <= 0
                && flow[next][cur] <= 0)continue;
                vis[next] = 1;
                q.push(next);
                par[next] = cur;
                if(next == t) {
                    maxflow += pushflow(t, inf);
                    pushed = true;
                    break;
                }
            }
            if(pushed)break;
        }
        if(!pushed)break;
    }
    return maxflow;
}

int main(){
    int m, u, v;
    scanf("%d%d",&n,&m);
    s = 2*n;
    t = 2*n+1;
    adj = vector<vector<int> > (2*n+10);
    int sum = 0;
    for(int i=0;i<n;++i){
        scanf("%d",&u);
        cap[s][i] = u;
        sum += u;
        adj[s].push_back(i);
        adj[i].push_back(s);
    }
    int check = 0;
    for(int i=0;i<n;++i){
        scanf("%d",&u);
        cap[i+n][t] = u;
        check += u;
        adj[i+n].push_back(t);
        adj[t].push_back(i+n);
    }
    if(sum != check) {
        printf("NO\n");
        return 0;
    }
    for(int i=0;i<n;++i){
        cap[i][i+n] = inf;
        adj[i].push_back(i+n);
        adj[i+n].push_back(i);
    }
    for(int i=0;i<m;++i){
        scanf("%d%d",&u,&v);
        u--; v--;
        cap[u][v+n] = inf;
        cap[v][u+n] = inf;
        adj[u].push_back(v+n);
        adj[v+n].push_back(u);
        adj[v].push_back(u+n);
        adj[u+n].push_back(v);
    }
    check = bfs();
    if(check == sum) {
        printf("YES\n");
        for(int i=0;i<n;++i){
            for(int j=0;j<n;++j){
                printf("%d ", flow[i][j+n]);
            }
            printf("\n");
        }
    } else {
        printf("NO\n");
    }
    return 0;
}