题意：给你初始状态和目标状态，再给你m条路，士兵只能通过路走到相邻城市去，一个士兵只能移动一次。问你能否到达该状态，如果能输出转移的矩阵
题解：很显然的网络流，将一个点拆成三个，一个初始状态与s连，一个目标状态与t连，容量b[i]，在建立一个中间点，连接初始状态容量INF和目标状态容量a[i]；记录下每个中间点和相邻点的边，再跑完网络流后，原容量减去残余流量就能得到转移的士兵个数
#include <iostream> #include <cstdio> #include <cmath> #include <algorithm> #include <map> #include <queue> #include <vector> #include <cstring> #include <iomanip> #include <set> #include<ctime> //CLOCKS_PER_SEC #define se second #define fi first #define ll long long #define Pii pair<int,int> #define Pli pair<ll,int> #define ull unsigned long long #define pb push_back #define fio ios::sync_with_stdio(false);cin.tie(0) const double Pi=3.14159265; const int N=1e6+10; const ull base=163; const int INF=0x3f3f3f3f; using namespace std; int n,m,s,t,tot=0; int head[900],nx[N],to[N],cap[N],cur[900]; void add(int u,int v,int c){ to[tot]=v; nx[tot]=head[u]; cap[tot]=c; head[u]=tot++; to[tot]=u; nx[tot]=head[v]; cap[tot]=0; head[v]=tot++; } int d[900]; bool bfs(){ memset(d,-1,sizeof(d)); queue<int>q; q.push(s); d[s]=1; while(!q.empty()){ int u=q.front();q.pop(); for(int i=head[u];~i;i=nx[i]){ int v=to[i]; if(d[v]==-1&&cap[i]>0){ d[v]=d[u]+1; q.push(v); } } } return d[t]!=-1; } int dfs(int s,int a){ if(s==t||a==0)return a; int flow=0,f; for(int &i=cur[s];~i;i=nx[i]){ int v=to[i]; if(d[s]+1==d[v] && cap[i]>0 && (f=dfs(v,min(a,cap[i])))>0){ flow+=f; cap[i]-=f; cap[i^1]+=f; a-=f; if(a==0)break; } } return flow; } int dinic(){ int ans=0; while(bfs()){ for(int i=0;i<=t;i++)cur[i]=head[i]; while(int di=dfs(s,INF)){ ans+=di; } } return ans; } int a[900],b[900]; int num[200][200]; pair<int,int>p[900]; int po[600]; int main(){ scanf("%d%d",&n,&m); t=600,s=0; memset(head,-1,sizeof(head)); int o=0; int oo=0; for(int i=1;i<=n;i++){ scanf("%d",&a[i]); oo+=a[i]; add(s,i,a[i]); num[i][i]=a[i]; add(i,i+n,INF); add(i+n,i+2*n,a[i]); } int sum=0; for(int i=1;i<=n;i++){ scanf("%d",&b[i]); add(i+2*n,t,b[i]); sum+=b[i]; } for(int i=1;i<=m;i++){ int u,v;scanf("%d%d",&u,&v); add(u+n,v+2*n,a[u]); p[++o].fi=u+n,p[o].se=v+2*n; po[o]=tot-2; add(v+n,u+2*n,a[v]); p[++o].fi=v+n,p[o].se=u+2*n; po[o]=tot-2; } int ans=dinic(); if(ans!=sum||oo!=sum)return cout<<"NO ",0; else { cout<<"YES "; for(int i=1;i<=o;i++){ int x=a[p[i].fi-n]-cap[po[i]]; if(x>0){ num[p[i].fi-n][p[i].se-2*n]+=x; num[p[i].fi-n][p[i].fi-n]-=x; } } for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ cout<<num[i][j]<<" "; } cout<<endl; } } return 0; }