网络流 最大流EK

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include <bits/stdc++.h>
using namespace std;
const int N=5100;
const long long INF=1e17;
int n,m,s,t,u,v;
long long w,ans,dis[N];
int cnt=0,vis[N],pre[N];
int head[N];
int flag[N][N];//重边
struct node {
	int to,nx;
	long long w;
} ed[N*2];
inline void add(int u,int v,long long w) {
	ed[++cnt].to=v;
	ed[cnt].w=w;
	ed[cnt].nx=head[u];
	head[u]=cnt;
	ed[++cnt].to=u;//反向边
	ed[cnt].w=0;
	ed[cnt].nx=head[v];
	head[v]=cnt;
}
inline int bfs() { //bfs寻找增广路 
	for( int i=1;i<=n;i++) vis[i]=0;
	queue<int> q;
	q.push(s);
	vis[s]=1;
	dis[s]=INF;
	while(!q.empty()) {
		int x=q.front();
		q.pop();
		for(int i=head[x];i!=-1;i=ed[i].nx) {
			if(ed[i].w==0) continue;//我们只关心剩余流量>0的边 
			int v=ed[i].to;
			if(vis[v]==1) continue; //这一条增广路没有访问过 
			dis[v]=min(dis[x],ed[i].w);
			pre[v]=i; //记录前驱，方便修改边权 
			q.push(v);
			vis[v]=1;
			if(v==t) return 1; //找到了一条增广路 
		}
	}
	return 0;
}
 
inline void update() { //更新所经过边的正向边权以及反向边权 
	int x=t;
	while(x!=s) {
		int v=pre[x];
		ed[v].w-=dis[t];
		ed[v^1].w+=dis[t];
		x=ed[v^1].to;
	}
	ans+=dis[t];  //累加每一条增广路经的最小流量值 
}
void solve(){
	cin>>n>>m>>s>>t;//n个点,m边，源点S，汇点t
	for(int i=0;i<=n;i++) head[i]=-1;
	cnt=1;//必须从1开始
	for(register int i=1;i<=m;i++) {
		cin>>u>>v>>w;
		if(flag[u][v]==0) { //处理重边的操作（加上这个模板题就可以用Ek算法过了） 
			add(u,v,w);
			flag[u][v]=cnt;
		}
		else {//重边容量+w
			ed[flag[u][v]-1].w+=w;
		}
	}
	while(bfs()!=0) { //直到网络中不存在增广路 
		update();
	}
	cout<<ans;
}
signed main() {
	solve();
	return 0;
}