Soldier and Traveling

传送门
题目要求士兵只能从所在城市移动一次或不移动
所以可以考虑从源点到汇点的网络流
将每个点 x 拆成入点 x 和出点 x+n，他们之间流量为 inf
源点为 0，汇点为 2n+1
源点到入点的流量限制为 a[i]
出点到汇点的流量限制为 b[i]
对于每一条边 x 和 y
x 的入点到 y 的出点建边，流量为 inf
y 的入点到 x 的出点建边，流量为 inf
对于样例一构图：

当 mxflow=sum a[i]=sum b[i]时
说明满足题意输出 yes
否则输出 no
对于士兵的流动，判断一下每条边流了多少流量即可

程序：

//by xxj
#include<bits/stdc++.h>
using namespace std;
#define mp make_pair
#define ll long long
#define pii pair<int,int>
#define lowbit(x) x&-x
using namespace std;
const int inf=1e9+7;
const double eps=1e-10;
const ll linf=1e18+7;
const ll hh=523;
//const int mod=;
const int maxn=207;
struct edge{
	int des,cap,rev;
};
vector<edge> G[maxn];
bool visited[maxn];
int a[maxn],b[maxn];
int ans[maxn][maxn];
int n,m;
int dfs(int s,int t,int f){
	visited[s]=true;
	if (s==t){
		return f;
	}
	for (int i=0;i<G[s].size();i++){
		edge e=G[s][i];
		if (!visited[e.des] && e.cap>0){
			int d=dfs(e.des,t,min(f,e.cap));
			if (d>0){
				G[s][i].cap-=d;
				G[e.des][e.rev].cap+=d;
				return d;
			}
		}
	}
	return 0;
}
int maxflow(){
	int flows=0;
	while(true){
		memset(visited,false,sizeof(visited));
		int f=dfs(0,2*n+1,inf);
		if (f==0){
			return flows;
		}
		flows+=f;
	}
}
int main(){
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	int x,y;
	scanf("%d%d",&n,&m);
	int suma=0,sumb=0; 
	for (int i=1;i<=n;i++){
		scanf("%d",a+i);
		suma+=a[i]; 
	}
	for (int i=1;i<=n;i++){
		scanf("%d",b+i);
		sumb+=b[i];
	}
	if (suma!=sumb){
		puts("NO");
		return 0;
	}
	for (int i=1;i<=n;i++){
		G[0].push_back((edge){i,a[i],G[i].size()});
		G[i].push_back((edge){0,0,G[0].size()-1});
	}
	for (int i=n+1;i<=2*n;i++){
		G[2*n+1].push_back((edge){i,0,G[i].size()});
		G[i].push_back((edge){2*n+1,b[i-n],G[2*n+1].size()-1});
	}
	for (int i=1;i<=n;i++){
		G[i].push_back((edge){i+n,inf,G[i+n].size()});
		G[i+n].push_back((edge){i,0,G[i].size()-1});
	}
	for (int i=1;i<=m;i++){
		int x,y;
		scanf("%d%d",&x,&y);
		G[x].push_back((edge){y+n,inf,G[y+n].size()});
		G[y+n].push_back((edge){x,0,G[x].size()-1});
		G[y].push_back((edge){x+n,inf,G[x+n].size()});
		G[x+n].push_back((edge){y,0,G[y].size()-1});
	} 
	int mx=maxflow();
	if (mx!=suma){
		puts("NO");
		return 0;
	}
	puts("YES");
	for (int i=1;i<=n;i++){
		for (int j=0;j<G[i].size();j++){
			if (G[i][j].des==0 || G[i][j].des==2*n+1){
				continue;
			}
			ans[i][G[i][j].des-n]=G[G[i][j].des][G[i][j].rev].cap;
		}
	}
	for (int i=1;i<=n;i++){
		printf("%d",ans[i][1]);
		for (int j=2;j<=n;j++){
			printf(" %d",ans[i][j]);
		}
		printf("\n");
	}
	return 0;
}
/*
input:
*/

​