Soldier and Traveling codeforces546E （最大流好题）

题目链接：http://codeforces.com/contest/546/problem/E

题意：给你n个城市，每个城市原来有ai个士兵，每个城市想要达到目标士兵数是bi， 士兵可以沿着某条路走  或者 在原来的城市不动，只能走一次。给你m条路，问能不能使得所有的城市满足目标

难点在于建图上。  由于士兵可以选择不移动，那么需要把城市拆点，一个当做起始点，一个当做目标点

m条边连接 的时候由于是无向边，所以需要addedge 两次

像下图

一个起点可以对应本身的终点（如果这条边有流量，相当于一些士兵 不移动，），也可以指向其他的终点（如果有流量，则代表有一些士兵走向了其他点）

 

先把初始值加起来做suma  再把目标值加起来做sumb  如果不相等 很明显输出NO

然后跑一遍最大流，如果最大流等于suma或者sumb  输出YES，并且输出流量的流向

如果不相等  输出NO

代码弱弱的献上，欢迎各位指正

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
using namespace std;
#define ll long long
#define INF 0x3f3f3f3f
const int maxn = 1e6+5;
struct node {
    int to;
    int cap;
    int rev;
    int flow;
    node(){}
    node(int a,int b,int d,int c=0):to(a),cap(b),rev(d),flow(c){}
};
vector<node> v[maxn];
int d[maxn],cur[maxn],n,m,p,s,t,cnt;
void addedge(int from,int to,int cap) {
    v[from].push_back(node(to,cap,v[to].size()));
    v[to].push_back(node(from,0,v[from].size()-1));
}
int dfs(int u,int flow) {
    if(u==t || !flow) return flow;
    int ans = 0;
    for(int &i = cur[u];i<v[u].size();i++) {
        node &e = v[u][i];
        if(d[e.to]  == d[u] + 1 && e.cap > 0) {
            int temp = dfs(e.to,min(flow,e.cap));
            if(temp>0) {
                flow-=temp;
                e.cap-=temp;
                v[e.to][e.rev].cap+=temp;
                e.flow+=temp;
                v[e.to][e.rev].flow-=temp;
                ans += temp;
                if(!flow) break;
            }
        }
    }
    if(!ans) d[u] = -1;
    return ans;
}

bool bfs() {
    for(int i=0;i<=t;i++) d[i] = -1;
    queue<int> q;
    q.push(s);
    d[s] = 0;
    while(!q.empty()) {
        int u = q.front();
        q.pop();
        for(int i=0;i<v[u].size();i++) {
            int to = v[u][i].to;
            if(d[to]==-1 && v[u][i].cap>0) {
                d[to] = d[u] + 1;
                q.push(to);
            }
        }
    }
    return (d[t] != -1);
}

int dinic() {
    int max_flow = 0,tt;
    while(bfs()) {
        for(int i=s;i<=t;i++) cur[i] = 0;
        while((tt = dfs(s,INF)) > 0) max_flow+=tt;
    }
    return max_flow;
}
int a[105],b[105],suma,sumb,ans,pos[105][105],x,y;
int main()
{

    scanf("%d%d",&n,&m);
    s = 0, t = 2 * n + 1;
    for(int i=1;i<=n;i++) {
        scanf("%d",&a[i]);
        suma+=a[i];
        addedge(0,i,a[i]);
        addedge(i,i+n,INF);
    }
    for(int i=1;i<=n;i++) {
        scanf("%d",&b[i]);
        sumb+=b[i];
        addedge(i+n,t,b[i]);
    }
    for(int i=0;i<m;i++) {
        scanf("%d %d",&x ,&y);
        addedge(x,y+n,INF);
        addedge(y,x+n,INF);
    }
    if(suma!=sumb) {
        puts("NO");
        return 0;
    }

    ans = dinic();
    if(ans == suma) {
        puts("YES");
        for(int i=1;i<=n;i++) {
            for(int j=0;j<v[i].size();j++) {
                node &e = v[i][j];
                if(e.to>0) pos[i][e.to-n] = e.flow;
            }
        }
        for(int i=1;i<=n;i++) {
            for(int j=1;j<=n;j++) {
                printf("%d ",pos[i][j]);
            }
            puts("");
        }
    }
    else {
        puts("NO");
    }
    return 0;
}