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