网络流题目最有意思的地方就是构图了，毕竟套模板每个人都会的
现在有一个矩阵，已知前i行元素之和a[i]（1<=i<=n），前j列元素之和b[j]（1<=j<=m），求一个可行的矩阵，且矩阵每个元素在区间[1,20]内。
这也算是含上下界的网络流了，但是显然，如果将每个元素都减一，就是普通的最大流了，矩阵元素值在区间[0,19]内。
首先求出第i行元素之和r[i]，第j列元素之和c[j]，
然后就是建图，每行化为一个结点1~n，每列化为一个结点n+1~n+m
源点到1~n，分别连一条边，容量为r[i]-m
n+1~n+m到汇点，分别连一条边，容量为c[i]-n
1~n到n+1~n+m，分别连一条容量为19的边
这样跑一发网络流
#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<set>
#include<map>
#include<stack>
#include<vector>
#include<queue>
#include<string>
#include<sstream>
#define MAXN 1000
#define MAXM 2000
#define INF (1<<30)
#define eps 0.000001
#define ALL(x) x.begin(),x.end()
#define INS(x) inserter(x,x.begin())
using namespace std;
const int inf = 0x3f3f3f3f;
int i,j,k,n,m,x,y,T,num,w,cas,s,t,maxflow,u;
struct edgenode
{
int from,to,next;
int cap;
}edge[MAXM];
int Edge,head[MAXN],ps[MAXN],dep[MAXN],r[MAXN],c[MAXN],tt;
int ans[MAXN][MAXN]; void add_edge(int x,int y,int c)
{
edge[Edge].from=x;
edge[Edge].to=y;
edge[Edge].cap=c;
edge[Edge].next=head[x];
head[x]=Edge++; edge[Edge].from=y;
edge[Edge].to=x;
edge[Edge].cap=;
edge[Edge].next=head[y];
head[y]=Edge++;
}
/*关于这个模板：
Edge为前向星的边数，所以需要初始化Edge和head数组
n表示有n个点，这个版无所谓点从0开始还是从1开始，s表示源点，t表示汇点
很好的一个是，这个版的DFS使用的是模拟栈，防止爆栈
*/ int dinic(int n,int s,int t)
{
int tr,res=;
int i,j,k,l,r,top;
while(){
memset(dep,-,(n+)*sizeof(int));
for(l=dep[ps[]=s]=,r=;l!=r;)//BFS部分，将给定图分层
{
for(i=ps[l++],j=head[i];j!=-;j=edge[j].next)
{
if (edge[j].cap&&-==dep[k=edge[j].to])
{
dep[k]=dep[i]+;ps[r++]=k;
if(k==t)
{
l=r;
break;
}
}
}
}
if(dep[t]==-)break; for(i=s,top=;;)//DFS部分
{
if(i==t)//当前点就是汇点时
{
for(k=,tr=inf;k<top;++k)
if(edge[ps[k]].cap<tr)tr=edge[ps[l=k]].cap; for(k=;k<top;++k)
edge[ps[k]].cap-=tr,edge[ps[k]^].cap+=tr; res+=tr;
i=edge[ps[top=l]].from;
} for(j=head[i];j!=-;j=edge[j].next)//找当前点所指向的点
if(edge[j].cap&&dep[i]+==dep[edge[j].to]) break; if(j!=-)
{
ps[top++]=j;//当前点有所指向的点，把这个点加入栈中
i=edge[j].to;
}
else
{
if (!top) break;//当前点没有指向的点，回溯
dep[i]=-;
i=edge[ps[--top]].from;
}
}
}
return res;
} int main()
{
scanf("%d",&T);
for (cas=;cas<=T;cas++)
{
memset(head,-,sizeof(head));
Edge=; scanf("%d%d",&n,&m);
int pre=;
for (i=;i<=n;i++)
{
scanf("%d",&r[i]);
add_edge(,i,r[i]-m-pre);
pre=r[i];
}
tt=n+m+;
pre=;
for (i=;i<=m;i++)
{
scanf("%d",&c[i]);
add_edge(i+n,tt,c[i]-n-pre);
pre=c[i];
}
for (i=;i<=n;i++)
{
for (j=;j<=m;j++)
{
add_edge(i,n+j,);
}
} maxflow=dinic(tt+,,tt);
//cout<<maxflow<<endl;
for (i=;i<=n;i++)
{
for (j=head[i];j!=-;j=edge[j].next)
{
u=edge[j].to;
if (u<=n||u>n+m) continue;
ans[i][u-n]=-edge[j].cap;
}
}
printf("Matrix %d\n",cas);
for (i=;i<=n;i++)
{
for (j=;j<m;j++)
{
printf("%d ",ans[i][j]+);
}
printf("%d\n",ans[i][m]+);
}
if (cas!=T) printf("\n");
}
return ;
}