CF546E
這題并不是太難
首先題目我們將每個城市拆點,由源點向一端連容量為初始人數的邊,由另一端向匯點連容量為最后人數的邊,然后按照題目要求從一端向另一端連容量無窮大的邊
這樣跑出最大流之后我們只需比較這個流量與總人數是否相等就知道是否合法了
至于輸出方案,一個點向另一個點的所有流量都會體現在反向邊上,因此我們只需最后統計反向邊即可
貼代碼:
#include <cstdio> #include <cmath> #include <cstring> #include <cstdlib> #include <iostream> #include <algorithm> #include <queue> #include <stack> using namespace std; const int inf=0x3f3f3f3f; struct Edge { int nxt; int to; int val; }edge[500005]; int head[5005]; int dis[5005]; int cur[5005]; int v0[5005],v1[5005]; int re[105][105]; int cnt=1; int n,m; int st,ed; int sum1=0,sum2=0; void add(int l,int r,int w) { edge[cnt].nxt=head[l]; edge[cnt].to=r; edge[cnt].val=w; head[l]=cnt++; } void dadd(int l,int r,int w) { add(l,r,w),add(r,l,0); } int ide(int x) { return x&1?x+1:x-1; } bool bfs() { memset(dis,0,sizeof(dis)); memcpy(cur,head,sizeof(head)); dis[st]=1; queue <int> M; M.push(st); while(!M.empty()) { int u=M.front(); M.pop(); for(int i=head[u];i;i=edge[i].nxt) { int to=edge[i].to; if(!dis[to]&&edge[i].val)dis[to]=dis[u]+1,M.push(to); } } return dis[ed]; } int dfs(int x,int lim) { if(x==ed)return lim; int ret=0; for(int i=cur[x];i;i=edge[i].nxt) { int to=edge[i].to; if(dis[to]==dis[x]+1&&edge[i].val) { int temp=dfs(to,min(lim,edge[i].val)); if(temp) { ret+=temp,lim-=temp; edge[i].val-=temp,edge[ide(i)].val+=temp; if(!lim)break; } } } return ret; } int dinic() { int ans=0; while(bfs())ans+=dfs(st,inf); return ans; } int main() { scanf("%d%d",&n,&m); st=2*n+1,ed=2*n+2; for(int i=1;i<=n;i++)scanf("%d",&v0[i]),dadd(st,i,v0[i]),sum1+=v0[i]; for(int i=1;i<=n;i++)scanf("%d",&v1[i]),dadd(i+n,ed,v1[i]),sum2+=v1[i]; if(sum1!=sum2){printf("NO\n");return 0;} for(int i=1;i<=n;i++)dadd(i,i+n,inf); for(int i=1;i<=m;i++) { int x,y; scanf("%d%d",&x,&y); dadd(x,y+n,inf),dadd(y,x+n,inf); } int t=dinic(); if(t==sum1) { printf("YES\n"); for(int i=1;i<=n;i++) { for(int j=head[i];j;j=edge[j].nxt) { int to=edge[j].to; if(to>n)re[i][to-n]=edge[ide(j)].val; } } for(int i=1;i<=n;i++,printf("\n"))for(int j=1;j<=n;j++)printf("%d ",re[i][j]); }else printf("NO\n"); return 0; }

浙公網安備 33010602011771號