## Monday, July 20, 2015

### 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];
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){
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;
int sum = 0;
for(int i=0;i<n;++i){
scanf("%d",&u);
cap[s][i] = u;
sum += u;
}
int check = 0;
for(int i=0;i<n;++i){
scanf("%d",&u);
cap[i+n][t] = u;
check += u;
}
if(sum != check) {
printf("NO\n");
return 0;
}
for(int i=0;i<n;++i){
cap[i][i+n] = inf;
}
for(int i=0;i<m;++i){
scanf("%d%d",&u,&v);
u--; v--;
cap[u][v+n] = inf;
cap[v][u+n] = inf;
}
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;
}