Soldier and Traveling

http://codeforces.com/contest/546/problem/E

题意：给定一张n个结点，m条边的无向图，再给定n个整数a[1],a[2]…a[n]代表初始时每个结点上驻守的士兵数量，每个结点的士兵可以在原地不动，也可以移动到与当前结点邻接的其他结点上去，但只能移动一次。现在问，能否通过合理的移动使得最终这n个结点驻守的士兵数量分别为b[1],b[2]…b[n]，如果可以输出”YES”，同时输出一个矩阵表示士兵的移动情况，矩阵的第u行第v列代表有多少个士开始在u结点，后来到了v结点，如果无解输出”NO”即可。

题解：网络流

建模，首先建立一个下标为0的源点和下标为n*2+1的汇点，然后把原来图中的每个结点u拆分成两个点，u和u+n，然后连接一条(u,u+n,inf)的有向边，代表士兵可以原地不动，同时把源点到各个点连接一条有向边(0,u,a[u])代表初始状态，同时连接各个点到汇点一条有向边(u,n*2+1,b[u])表示最后的状态，然后跑最大流算法，如果最大流的值等于数组a的总和和数组b的总和，那就说明问题有解，否则无解。

有个坑点是题目不保证数组a,b的和相同。

/*
*@Author:   STZG
*@Language: C++
*/

#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG
#define RI register int
#define endl "\n"
using namespace std;
typedef long long ll;
//typedef __int128 lll;
const int N=400+10;
const int M=100000+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
int s,t,n,m,k,p,l,r,u,v,w,c2;
int ans,cnt,flag,temp,sum;
int dis[N],a[N],b[N];
int mp[N][N];
struct node{
    int u,v,c;
    node(){};
    node(int form,int to,int cap):u(form),v(to),c(cap){}
};
vector<node>edge;
vector<int> G[N];
void Addedge(int u,int v,int cap){
    edge.push_back({u,v,cap});
    edge.push_back({v,u,0});
    int sz=edge.size();
    G[u].push_back(sz-2);
    G[v].push_back(sz-1);
}
bool bfs(int u){
    memset(dis,-1,sizeof(dis));
    dis[u]=0;
    queue<int>q;
    q.push(u);
    while(!q.empty()){
        int u=q.front();
        q.pop();
        for(int i=0;i<G[u].size();i++){
            node e=edge[G[u][i]];//cout<<u<<" "<<e.v<<endl;
            if(dis[e.v]<0&&e.c>0){
                dis[e.v]=dis[u]+1;
                q.push(e.v);
            }
        }
    }
    return dis[t]>0;
}
int dfs(int u,int flow){
    if(u==t)
        return flow;
    int now;
    for(int i=0;i<G[u].size();i++){
        node e=edge[G[u][i]];
        if(e.c>0&&dis[u]+1==dis[e.v]&&(now=dfs(e.v,min(flow,e.c)))){
            edge[G[u][i]].c-=now;
            edge[G[u][i]^1].c+=now;
            return now;
        }
    }
    return 0;
}
void dinic(){
    while(bfs(s)){
        int res=0;
        while(res=dfs(s,INF)){
            ans+=res;
        }
    }
}
void init(){
    s=0;t=2*n+1;
    for(int i=s;i<=t;i++)G[i].clear();
    edge.clear();
    ans=0;
    sum=0;
}
int main()
{
#ifdef DEBUG
	freopen("input.in", "r", stdin);
	//freopen("output.out", "w", stdout);
#endif
    //ios::sync_with_stdio(false);
    //cin.tie(0);
    //cout.tie(0);
    //scanf("%d",&t);
    //int T=0;
    while(~scanf("%d%d",&n,&m)){
        init();
        for(int i=1;i<=n;i++)scanf("%d",&a[i]),sum+=a[i];
        temp=sum;
        for(int i=1;i<=n;i++)scanf("%d",&b[i]),sum-=b[i];
        for(int i=1;i<=n;i++)Addedge(s,i,a[i]);
        for(int i=1;i<=n;i++)Addedge(i,i+n,INF);
        for(int i=1;i<=m;i++){
            scanf("%d%d",&u,&v);
            Addedge(u,v+n,INF);
            Addedge(v,u+n,INF);
        }
        for(int i=1;i<=n;i++)Addedge(i+n,t,b[i]);
        if(sum){
            cout<<"NO"<<endl;
            continue;
        }
        dinic();
        //cout<<ans<<endl;
        if(ans==temp){
            cout<<"YES"<<endl;
            for(int i=1;i<edge.size();i+=2){
                if(1+n<=edge[i].u&&edge[i].u<=n*2&&1<=edge[i].v&&edge[i].v<=n&&edge[i].c>0)
                    mp[edge[i].v][edge[i].u-n]=edge[i].c;
            }
            for(int i=1;i<=n;i++)
                for(int j=1;j<=n;j++)
                    printf("%d%c",mp[i][j]," \n"[j==n]);
        }else{
            cout<<"NO"<<endl;
        }
    }

#ifdef DEBUG
	printf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC);
#endif
    //cout << "Hello world!" << endl;
    return 0;
}