★★☆ 输入文件：flowa.in 输出文件：flowa.out 简单对比
时间限制：1 s 内存限制：128 MB
【问题描述】
Bob 觉得一般图的最大流问题太难了，他不知道如何解决，于是他想尝试一个简单点的：栅格网络中的最大流问题，这个虽说简单了一点，但对 Bob 来说依旧太难，现在他有个麻烦需要你帮忙：给你一个 N*M 的栅格（如下所示），栅格中的边表示可以流水的管道，边上的数字表示管道的容量，举例说明：在下面图（ 2.6.1 ）中， (0,0) 和 (1,0) 之间边的容量为 6 ，这意味着这条边（水管）的最大水流量不超过 6 个单位。
N=3 M=3
图 2.6.1 栅格网络流
那么栅格中从 S 到 T 的最大流是多少呢 ? 换句话说 , 某一时刻最多能有多少单位的水从 S 流向 T?
【输入格式】
输入文件的第一行是一个正整数 T ，表示接下来有多少组测试数据。
每一组测试数据的第一行有两个正整数 N,M(1<=N,M<=100)<n<100) 和="" m(1<m<100)="" 。接下来有两个整数矩阵="" h="" （="" n*(m-1)="" ）和="" v="" (n-1)*m="" ），="" h[i][j]="" 表示="" (i,j)="" 与="" (i,j+1)="" 之间边的容量，="" v[i][j]="" (i+1,j)="" 中所有的数均非负且小于="" 10^10="" 。<="" p="">
接着有两个矩阵H(N*(M-1)),V((N-1)*M)，H[i][j]表示(i,j)->(i,j+1)的流量；
V[i][j]表示(i,j)->(i+1,j)的流量。
【输出格式】
每一组测试数据输出只有一行，包含一个整数，即从 S(0,0) 到 T(N-1,M-1) 的栅格网络的最大流，不允许出现多余的空格。
【输入样例】
输入文件名： flowa .in
1
3 3
0 1
2 3
4 5
6 7 8
9 10 11
输出文件名： flowa .out
6
提示：下图 (2.6.2) 所示即为样例中栅格中的一个最大流。
N=3 M=3
图 2.6.2 一个解决方案
妈蛋
dfs return res 写成了 return true
找了好久
#include <cstring>
#include <cstdio>
#include <queue>
#define N 100000
#define inf 0x3f3f3f3f using namespace std;
int t,n,m,cnt=,S,T,to[N<<],cur[N],dep[N],head[N],nextt[N<<],flow[N<<];
inline void ins(int u,int v,int f)
{
nextt[++cnt]=head[u];to[cnt]=v;flow[cnt]=f;head[u]=cnt;
nextt[++cnt]=head[v];to[cnt]=u;flow[cnt]=f;head[v]=cnt;
}
bool bfs()
{
for(int i=S;i<=T;++i) dep[i]=-,cur[i]=head[i];
dep[S]=;
queue<int>q;
q.push(S);
for(int u;!q.empty();)
{
u=q.front();
q.pop();
for(int i=head[u];i;i=nextt[i])
{
int v=to[i];
if(dep[v]==-&&flow[i])
{
dep[v]=dep[u]+;
q.push(v);
}
}
}
if(dep[T]!=-) return true;
else return false;
}
inline int min(int a,int b) {return a>b?b:a;}
int dfs(int u,int limit)
{
if(u==T||!limit) return limit;
int f,res=;
for(int &i=cur[u];i;i=nextt[i])
{
int v=to[i];
if(dep[v]==dep[u]+&&flow[i]&&(f=dfs(v,min(flow[i],limit))))
{
res+=f;
limit-=f;
flow[i]-=f;
flow[i^]+=f;
if(!limit) break;
}
}
if(res!=limit) dep[u]=-;
return res;
}
inline void init()
{
cnt=;
memset(head,,sizeof(head));
}
int main(int argc,char *argv[])
{
freopen("flowa.in","r",stdin);
freopen("flowa.out","w",stdout);
scanf("%d",&t);
for(;t--;)
{
scanf("%d%d",&n,&m);
S=,T=n*m;
for(int i=;i<=n;++i)
for(int a,j=;j<m;++j)
{
scanf("%d",&a);
if(a) ins((i-)*m+j,(i-)*m+j+,a);
}
for(int i=;i<n;++i)
for(int a,j=;j<=m;++j)
{
scanf("%d",&a);
if(a) ins((i-)*m+j,i*m+j,a);
}
int ans=;
while(bfs()) ans+=dfs(S,inf);
printf("%d\n",ans);
init();
}
fclose(stdin); fclose(stdout);
return ;
}