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