#include<bits/stdc++.h>
using namespace std;
#define maxn 1005
#define ll long long
const ll inf =
0x3f3f3f3f3f3f3f3f;
struct Edge{ll to,nxt,w;}e[maxn<<
1];
int head[maxn],tot,n,m;
void init(){
memset(e,0,
sizeof e);
memset(head,-
1,
sizeof head);
tot=
0;
}
void add(ll u,ll v,ll w){
e[tot].to=v;e[tot].nxt=head[u];e[tot].w=w;head[u]=tot++
;
}
int d[maxn];
bool bfs(){
//在残量网络上构造分层图
memset(d,
0,
sizeof d);
queue<
int>
q;
while(q.size())q.pop();
q.push(1);d[
1]=
1;
while(q.size()){
int x=
q.front();q.pop();
for(
int i=head[x];i!=-
1;i=
e[i].nxt){
int y=
e[i].to;
if(d[y] || e[i].w==
0)
continue;
q.push(y);
d[y]=d[x]+
1;
if(y==n)
return 1;
}
}
return 0;
}
int dinic(
int x,ll flow){
if (x==n)
return flow;
ll rest=
flow;
for(
int i=head[x];i!=-
1 && rest>
0;i=
e[i].nxt){
int y=
e[i].to;
if(e[i].w==
0 || d[y]!=d[x]+
1)
continue;
ll k=
dinic(y,min(rest,e[i].w));
if(!k) d[y]=
0;
//y点已经被增广完毕
e[i].w-=k; e[i^
1].w+=
k;
rest-=
k;
}
return flow-
rest;
}
int main(){
while(cin>>m>>
n){
init();
for(
int i=
1;i<=m;i++
){
ll u,v,w;
cin>>u>>v>>
w;
add(u,v,w);
add(v,u,0);
}
ll flow=
0,ans=
0;
while(bfs())
while(flow=dinic(
1,inf))
ans+=
flow;
cout<<ans<<
'\n';
}
}
转载于:https://www.cnblogs.com/zsben991126/p/10987746.html
