传送门
题目要求士兵只能从所在城市移动一次或不移动
所以可以考虑从源点到汇点的网络流
将每个点 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:
*/
欢迎来到这里!
我们正在构建一个小众社区,大家在这里相互信任,以平等 • 自由 • 奔放的价值观进行分享交流。最终,希望大家能够找到与自己志同道合的伙伴,共同成长。
注册 关于