概念： 水厂（不能流多了），管子（每一个管子有流量），小区
一般管子都是给的 残量， 连通器原理
求流到小区的最大流量；
Dinic 算法 时间复杂度 n^2m;
#include <bits/stdc++.h>
using namespace std;
#define ri register int
#define M 100005
template <class G> void read(G &x)
{
x=0;int f=0;char ch=getchar();
while(ch<'0'||ch>'9'){f|=(ch=='-');ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
x=f?-x:x;
return ;
}
int n,m,s,t;
int cent=1;
int head[M],nxt[M],to[M];
long long val[M];
void add(int a,int b,int c)
{
val[++cent]=c;
to[cent]=b;
nxt[cent]=head[a];
head[a]=cent;
}
int dep[205];
int bfs()
{
memset(dep,0,sizeof(dep));
queue<int> q;
q.push(s);
dep[s]=1; /// 很重要
while(!q.empty())
{
int a=q.front();q.pop();
for(ri p=head[a];p;p=nxt[p]) //
{
int b=to[p];
if(dep[b]==0&&val[p]) dep[b]=dep[a]+1,q.push(b);
}
}
return dep[t];
}
long long dfs(int a,long long in)
{
if(a==t) return in;
long long out =0;
for(ri p=head[a];p&∈p=nxt[p])
{
int b=to[p];
if(dep[b]==dep[a]+1&&val[p])
{
int res=dfs(b,min(in,val[p]));
val[p]-=res;
val[p^1]+=res;
in -=res;
out+=res;
}
}
if(out==0)
{
dep[a]=0;
}
return out;
}
int main(){
read(n);read(m);read(s);read(t);
for(ri i=1;i<=m;i++)
{
int a,b;
long long c;
read(a);read(b);read(c);
add(a,b,c);
add(b,a,0);
}
long long ans=0;
while(bfs())
{
ans+=dfs(s,1e18);
}
printf("%lld\n",ans);
return 0;
}
View Code