CF546E Soldier and Traveling
题目描述
In the country there are n n n cities and m m m bidirectional roads between them. Each city has an army. Army of the i i i -th city consists of ai a_{i} ai soldiers. Now soldiers roam. After roaming each soldier has to either stay in his city or to go to the one of neighboring cities by at moving along at most one road.
Check if is it possible that after roaming there will be exactly bi b_{i} bi soldiers in the i i i -th city.
输入输出格式
输入格式:
First line of input consists of two integers n n n and m m m ( 1<=n<=100 1<=n<=100 1<=n<=100 , 0<=m<=200 0<=m<=200 0<=m<=200 ).
Next line contains n n n integers a1,a2,...,an a_{1},a_{2},...,a_{n} a1,a2,...,an ( 0<=ai<=100 0<=a_{i}<=100 0<=ai<=100 ).
Next line contains n n n integers b1,b2,...,bn b_{1},b_{2},...,b_{n} b1,b2,...,bn ( 0<=bi<=100 0<=b_{i}<=100 0<=bi<=100 ).
Then m m m lines follow, each of them consists of two integers p p p and q q q ( 1<=p,q<=n 1<=p,q<=n 1<=p,q<=n , p≠q p≠q p≠q ) denoting that there is an undirected road between cities p p p and q q q .
It is guaranteed that there is at most one road between each pair of cities.
输出格式:
If the conditions can not be met output single word "NO".
Otherwise output word "YES" and then n n n lines, each of them consisting of n n n integers. Number in the i i i -th line in the j j j -th column should denote how many soldiers should road from city i i i to city j j j (if i≠j i≠j i≠j ) or how many soldiers should stay in city i i i (if i=j i=j i=j ).
If there are several possible answers you may output any of them.
输入输出样例
4 4
1 2 6 3
3 5 3 1
1 2
2 3
3 4
4 2
YES
1 0 0 0
2 0 0 0
0 5 1 0
0 0 2 1
2 0
1 2
2 1
NO
Solution:
本题最大流,建图贼有意思。
题意就是给定一些点上的初始士兵数,问能否通过相邻间的互相移动(只能邻边之间移动一次),达到每个点的目标士兵数。
首先我们可以特判出一个非法情况:$\sum\limits_{i=1}^{i\leq n}{a_i}\neq\sum\limits_{i=1}^{i\leq n}{b_i}$直接无解。
然后网络流的建图比较常规,源点$s\rightarrow i$边权为$a_i$,$i\rightarrow j$($i==j$或者$i$与$j$相邻)边权为$inf$,$j\rightarrow t$边权为$b_j$。跑出最大流后,判断总流量是否等于$a$的和,输出方案只要扫下中间连的反向边就好了。
代码:
#include<bits/stdc++.h>
#define il inline
#define ll long long
#define For(i,a,b) for(int (i)=(a);(i)<=(b);(i)++)
#define Bor(i,a,b) for(int (i)=(b);(i)>=(a);(i)--)
#define debug printf("%d %s\n",__LINE__,__FUNCTION__)
using namespace std;
const int N=,M=,inf=;
int n,m,s,t=,a[N],b[N],to[M],net[M],w[M],cnt=,h[N],dis[N];
int mp[N][N];
bool f; il int gi(){
int a=;char x=getchar();bool f=;
while((x<''||x>'')&&x!='-')x=getchar();
if(x=='-')x=getchar(),f=;
while(x>=''&&x<='')a=(a<<)+(a<<)+x-,x=getchar();
return f?-a:a;
} il void add(int u,int v,int c){to[++cnt]=v,net[cnt]=h[u],w[cnt]=c,h[u]=cnt;} il bool bfs(){
queue<int>q;
memset(dis,-,sizeof(dis));
q.push(s),dis[s]=;
while(!q.empty()){
int u=q.front();q.pop();
for(int i=h[u];i;i=net[i])
if(dis[to[i]]==-&&w[i])dis[to[i]]=dis[u]+,q.push(to[i]);
}
return dis[t]!=-;
} il int dfs(int u,int op){
if(u==t)return op;
int flow=,used=;
for(int i=h[u];i;i=net[i]){
int v=to[i];
if(dis[v]==dis[u]+&&w[i]>){
used=dfs(v,min(w[i],op));
if(!used)continue;
flow+=used,op-=used;
w[i]-=used,w[i^]+=used;
if(!op)break;
}
}
if(!flow)dis[u]=-;
return flow;
} il void init(){
n=gi(),m=gi();
For(i,,n) a[i]=gi(),add(s,i,a[i]),add(i,s,); For(i,,n) b[i]=gi(),add(i+n,t,b[i]),add(t,i+n,);
int u,v,c;
For(i,,m) u=gi(),v=gi(),add(u,v+n,inf),add(v+n,u,),add(v,u+n,inf),add(u+n,v,);
For(i,,n) add(i,i+n,inf),add(i+n,i,);
} il void solve(){
init();
int ans=,ta=,tb=;
For(i,,n) ta+=a[i],tb+=b[i];
if(ta!=tb) puts("NO");
else {
while(bfs())ans+=dfs(s,inf);
if(ans!=ta)puts("NO");
else {
puts("YES");
For(u,,n) {
for(int i=h[u+n];i;i=net[i])
if(w[i]!=inf&&to[i]!=t) mp[to[i]][u]=w[i];
}
For(i,,n) {For(j,,n) printf("%d ",mp[i][j]); printf("\n");}
}
}
} int main(){
solve();
return ;
}
最新文章
- .NET开发笔记(二十三) 谷歌地图下载
- NueGet设置package Source
- eclipse 编译android程序 编译错误
- JavaEE web.xml 中ContextLoaderListener的解析
- 慕课linux学习笔记(二)Xshell与虚拟机的连接
- thymleaf th:text=";|第${user.courseSort}课|"; 对于不知道的真的是解渴了
- C#的修饰符
- hdu1003 Max Sum(最大子串)
- vue中的import、export、requre的区别
- html学习笔记——ife task0001
- 06:vuejs项目实战
- [翻译]60,000毫秒内对Linux进行性能诊断
- 01: html常用标签
- swift 设置图片动画组 iOS11之前 默认图片 设置不成功
- app crawler1
- SqlMapConfig.xml配置文件的配置内容
- 怎样将word中的图片插入到CSDN博客中
- Linux命令-压缩解压命令:bzip2、bunzip2
- C#之多线程
- 视频分析(MATLAB)——MV分镜头图像分类