草地排水AC代码
```cpp
#include<cstdio>
#include<iostream>
using namespace std;
long long to[401],s[401],last[401],head[201],n,m;
int a[201],b[201],d[201];
long long p=0;
void add(int u,int v,int w)
{
p++;
last[p]=head[u];
s[p]=w;
to[p]=v;
head[u]=p;
}
bool bfs()
{
int hed=0,tail=1;
a[1]=1;
b[1]=1;
d[1]=1;
while(hed<tail)
{
hed++;
int j=head[a[hed]];
while(j!=0)
{
if(!b[to[j]]&&s[j]>0)
{
tail++;
a[tail]=to[j];
b[to[j]]=d[tail]=d[hed]+1;
}
j=last[j];
}
}
if(b[n])
return 1;
return 0;
}
int dfs(long long now,long long mint)
{
if(now==n||mint<=0)
return mint;
int j=head[now];
while(j!=0)
{
int t1;
if(b[now]+1==b[to[j]]&&s[j]>0)
{
t1=dfs(to[j],min(mint,s[j]));
if(t1>0)
{
s[j]-=t1;
s[j^1]+=t1;
return t1;
}
}
j=last[j];
}
}
int main()
{
long long t1,t2,t3;
scanf("%d%d",&m,&n);
for(int j=1;j<=m;j++)
{
scanf("%d%d%d",&t1,&t2,&t3);
add(t1,t2,t3);
add(t2,t1,0);
}
/*add((i-1)*n+j,(i-1)*n+j+1,t);
add((i-1)*n+j+1,(i-1)*n+j,t);
}
for(int i=1;i<=n-1;i++)
for(int j=1;j<=m;j++)
{
scanf("%d",&t);
add((i-1)*n+j,i*n+j,t);
add(i*n+j,(i-1)*n+j,t);
}
for(int i=1;i<=n-1;i++)
for(int j=1;j<=m-1;j++)
{
scanf("%d",&t);
add((i-1)*n+j,i*n+j+1,t);
add(i*n+j+1,(i-1)*n+j,t);
}*/
int t;
long long ans=0;
while(bfs())
{
while(t=dfs(1,0x7ffffff))
ans+=t;
for(int i=1;i<=n;i++)
b[i]=0;
}
cout<<ans<<endl;
return 0;
}
```
by 星灵王 @ 2018-02-26 14:08:36
本题AC代码
```cpp
#include<cstdio>
#include<iostream>
using namespace std;
long long to[200001],s[200001],last[200001],head[10001],n,m,s1,t4;
int a[10001],b[10001],d[10001];
long long p=0;
void add(int u,int v,int w)
{
p++;
last[p]=head[u];
s[p]=w;
to[p]=v;
head[u]=p;
}
bool bfs()
{
int hed=0,tail=1;
a[1]=s1;
b[s1]=1;
d[1]=1;
while(hed<tail)
{
hed++;
int j=head[a[hed]];
while(j!=0)
{
if(!b[to[j]]&&s[j]>0)
{
tail++;
a[tail]=to[j];
b[to[j]]=d[tail]=d[hed]+1;
}
j=last[j];
}
}
if(b[t4])
return 1;
return 0;
}
int dfs(long long now,long long mint)
{
if(now==t4||mint<=0)
return mint;
int j=head[now];
while(j!=0)
{
int t1;
if(b[now]+1==b[to[j]]&&s[j]>0)
{
t1=dfs(to[j],min(mint,s[j]));
if(t1>0)
{
s[j]-=t1;
// s[j^1]+=t1;
return t1;
}
}
j=last[j];
}
}
int main()
{
long long t1,t2,t3;
scanf("%d%d%d%d",&n,&m,&s1,&t4);
for(int j=1;j<=m;j++)
{
scanf("%d%d%d",&t1,&t2,&t3);
add(t1,t2,t3);
// add(t2,t1,0);
}
/*add((i-1)*n+j,(i-1)*n+j+1,t);
add((i-1)*n+j+1,(i-1)*n+j,t);
}
for(int i=1;i<=n-1;i++)
for(int j=1;j<=m;j++)
{
scanf("%d",&t);
add((i-1)*n+j,i*n+j,t);
add(i*n+j,(i-1)*n+j,t);
}
for(int i=1;i<=n-1;i++)
for(int j=1;j<=m-1;j++)
{
scanf("%d",&t);
add((i-1)*n+j,i*n+j+1,t);
add(i*n+j+1,(i-1)*n+j,t);
}*/
int t;
long long ans=0;
while(bfs())
{
while(t=dfs(s1,0x7ffffff))
ans+=t;
for(int i=1;i<=n;i++)
b[i]=0;
}
cout<<ans<<endl;
return 0;
}
```
by 星灵王 @ 2018-02-26 14:09:12
哪位大佬可以解释一下
by 星灵王 @ 2018-02-26 14:09:28
建议您去Loj.ac的101提交一下
洛谷这类模板的数据普遍很水
by Flaranis @ 2018-02-26 14:16:00
但是我加了反向边过了呀。。。
by 小可爱三岁七 @ 2018-02-26 15:27:09
AC代码：
by 小可爱三岁七 @ 2018-02-26 15:27:26
不对。。。。好像就是不用加反向边233....
by 小可爱三岁七 @ 2018-02-26 15:28:54
@[星灵王stark](/space/show?uid=38031) 您建边应该从0或2```
```
if(t1>0)
{
s[j]-=t1;
s[j^1]+=t1;
return t1;
}
```
开始建吧。。。
这样好对应反向边
j^1对应j的反向边。。。
您这种建边方式j^1对应下一条边。。。
by Dispwnl @ 2018-02-26 16:38:48
知道了，谢谢大佬
by 星灵王 @ 2018-02-27 13:07:13
嗯
数据太水
所以还是要加反向边
emmmmmmmm
by Aoki_灏 @ 2018-03-24 16:21:42