#include <iostream>
#include <cstdlib>
#include <stdio.h>
#include <map>
#include <cstring>
#include <math.h>
#include <stdlib.h>
#define ll long long
#define INF 0x3f3f3f3f
#define cle(a) memset(a,0,sizeof(a))
using namespace std;
struct G{
int v,cap,next;
}E[600010];
int pre[
1100],l,d[
1100],p[
1100];
int Q[
1100];
void init(){
l=
0;
memset(pre,-
1,
sizeof pre);
}
void add(
int u,
int v,
int cap){
E[l].v=
v;
E[l].cap=
cap;
E[l].next=
pre[u];
pre[u]=l++
;
}
bool bfs(
int s,
int e,
int n){
int i,u,v,head,tail;
for(i=
0;i<=n;i++)d[i]=-
1;
head=tail=
0;
d[s]=
0;
Q[tail]=
s;
while(head<=
tail){
u=Q[head++
];
for(i=pre[u];i+
1;i=
E[i].next){
v=
E[i].v;
if(d[v]==-
1&&E[i].cap>
0){
d[v]=d[u]+
1;
Q[++tail]=
v;
}
}
}
return (d[e]!=-
1);
}
int dfs(
int u,
int &e,
int f){
if(u==e||f==
0)
return f;
int flow=
0,tmp;
for(;p[u]+
1;p[u]=
E[p[u]].next){
G& en=
E[p[u]];
if(d[u]+
1==
d[en.v]){
tmp=
dfs(en.v,e,min(f,en.cap));
if(tmp>
0){
en.cap-=
tmp;
E[p[u]^
1].cap+=
tmp;
flow+=
tmp;
f-=
tmp;
if(f==
0)
break;
}
}
}
return flow;
}
int dinic(
int s,
int e,
int n){
int i,ans=
0;
while(bfs(s,e,n)){
for(i=
0;i<=n;i++)p[i]=
pre[i];
ans+=
dfs(s,e,INF);
}
return ans;
}
int x,y,w;
int main()
{
int n,m;
while(cin>>m>>
n){
init();
for(
int i=
1;i<=m;i++
){
scanf("%d%d%d",&x,&y,&
w);
add(x,y,w);
add(y,x,0);
}
printf("%d\n",dinic(
1,n,n));
//源点1汇点n
}
return 0;
}
转载于:https://www.cnblogs.com/pk28/p/4895895.html
相关资源：垃圾分类数据集及代码
