题意：知道矩阵的前i行之和，和前j列之和（任意i和j都可以）。求这个矩阵。每个格子中的元素必须在1~20之间。矩阵大小上限20*20
#include<cstdio> #include<cstring> #include<algorithm> #include<queue> #include<vector> #define pb push_back using namespace std; const int INF=0x3f3f3f3f; int ans[25][25],R,C,r[25],c[25],A[25],B[25]; struct EdmondsKarp { struct Edge { int from,to,cap,flow; }; vector<Edge>edges; vector<int>G[45]; int p[45],a[45]; void init() { for(int i=0;i<45;i++)G[i].clear(); edges.clear(); memset(p,0,sizeof(p)); } void addedge(int from,int to,int cap) { edges.pb((Edge){from,to,cap,0}); edges.pb((Edge){to,from,0,0}); int m=edges.size(); G[from].pb(m-2); G[to].pb(m-1); } int maxflow(int s,int t) { int flow=0; while(1) { memset(a,0,sizeof(a)); queue<int>q; q.push(s); a[s]=INF; while(!q.empty()) { int x=q.front(); q.pop(); for(int i=0;i<G[x].size();i++) { Edge& e=edges[G[x][i]]; if(!a[e.to]&&e.cap>e.flow) { p[e.to]=G[x][i]; a[e.to]=min(a[x],e.cap-e.flow); q.push(e.to); } } if(a[t])break; } if(!a[t])break; for(int u=t;u!=s;u=edges[p[u]].from) { edges[p[u]].flow+=a[t]; edges[p[u]^1].flow-=a[t]; } flow+=a[t]; } return flow; } void solve() { int temp=maxflow(0,R+C+1); for(int len=edges.size(),i=0;i<len;i+=2) { Edge& e=edges[i]; if(e.from!=0&&e.to!=R+C+1) ans[e.from][e.to-R]=e.flow+1; } for(int i=1;i<=R;i++) for(int j=1;j<=C;j++) printf(j==C?"%d ":"%d ",ans[i][j]); } }EK; int main() { int T; scanf("%d",&T); bool flag=0; for(int kase=1;kase<=T;kase++) { scanf("%d%d",&R,&C); EK.init(); for(int i=1;i<=R;i++)scanf("%d",&r[i]); for(int i=1;i<=R;i++)A[i]=r[i]-r[i-1]; for(int i=1;i<=C;i++)scanf("%d",&c[i]); for(int i=1;i<=C;i++)B[i]=c[i]-c[i-1]; for(int i=1;i<=R;i++) EK.addedge(0,i,A[i]-C); for(int i=1;i<=C;i++) EK.addedge(i+R,R+C+1,B[i]-R); for(int i=1;i<=R;i++) for(int j=1;j<=C;j++) EK.addedge(i,R+j,19); if(kase>1)putchar(' '); printf("Matrix %d ",kase); EK.solve(); } return 0; }