[文章目录]
Description
在农夫约翰的农场上,每逢下雨,贝茜最喜欢的三叶草地就积聚了一潭水.这意味着草地被水淹没了,并且小草要继续生长还要花相当长一段时间.因此,农夫约翰修建了一套排水系统来使贝茜的草地免除被大水淹没的烦恼（不用担心,雨水会流向附近的一条小溪）.作为一名一流的技师,农夫约翰
已经在每条排水沟的一端安上了控制器,这样他可以控制流入排水沟的水流量.
农夫约翰知道每一条排水沟每分钟可以流过的水量,和排水系统的准确布局（起点为水潭而终点为小溪的一张网）.需要注意的是,有些时候从一处到另一处不只有一条排水沟.
根据这些信息,计算从水潭排水到小溪的最大流量.对于给出的每条排水沟,雨水只能沿着一个方向流动,注意可能会出现雨水环形流动的情形.
网络流模板题，Dinic。Dinic算法的时间复杂度的理论上界是O(N^2*M)（N是结点数，M是边数），但实际上Dinic算法比这个理论上界好得多。如果所有边容量均为1，那么时间复杂度是O(min(N^0.67,M^0.5)*M)；对于二分图最大匹配这样的特殊图，时间复杂度是O(N^0.5*M)。
然后建图的时候反向弧的流量为 0。因为流量是单向的。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
int n,m,ans;
int dis[300];
queue<int> q;
int head[210],to[500],nxt[500],f[500],cnt=1;
void add(int x,int y,int z)
{
to[++cnt]=y;
nxt[cnt]=head[x];
f[cnt]=z;
head[x]=cnt;
}
bool bfs()
{
memset(dis,-1,sizeof(dis));
while(!q.empty()) q.pop();
q.push(1),dis[1]=0;
while(q.size())
{
int x=q.front();q.pop();
for(int y,i=head[x];i;i=nxt[i])
if(f[i]&&dis[y=to[i]]<0)
{
dis[y]=dis[x]+1;
q.push(y);
if(y==n) return true;
}
}
return false;
}
int dinic(int x,int flow)
{
int cc,tmp=flow;
if(x==n) return flow;
for(int y,i=head[x];i;i=nxt[i])
if(f[i]>0&&dis[y=to[i]]==dis[x]+1)
{
cc=dinic(y,min(f[i],tmp));
if(cc==0) dis[y]=-1;
tmp-=cc;f[i]-=cc;f[i^1]+=cc;
if(tmp==0) break;
}
return flow-tmp;
}
int main()
{
scanf("%d%d",&m,&n);
for(int x,y,z,i=1;i<=m;i++)
{
scanf("%d%d%d",&x,&y,&z);
add(x,y,z);add(y,x,0);
}
while(bfs())
ans+=dinic(1,1<<30);
printf("%d",ans);
return 0;
}