网络最大流（EK算法）

网络流EK算法主要是以bfs为主，寻找一条增广路。 增广路算法的关键是 寻找增广路 和 改进网络流。 1. bfs判断由从源点到汇点是否联通，并寻找到这条增广路； 2. 更新路径上的流量，正向边减去流量，反向弧加上流量； 3. 重复执行1过程，直到找不到增广路。 ~~不懂是吗，其实我也不懂为啥要加反向边~~ 创建反向弧是因为在其他增广路要经过这条路径时，要将此路径上的流量反推过去，实现流量最大化。 emmm，我知道其实自己说的很绕。。。 但是多读读下面的模板代码应该就能理解，毕竟我又不擅长写那种难以读懂的代码。 邻接矩阵实现 ```cpp #include <queue> #include <cstdio> #include <cstring> #include <iostream> #define ms(n,x) memset(n,x,sizeof(n)) using namespace std; const int MAXN = 300; const int MAX_INT = ((1 << 30) - 1); int s,t; int n,m; bool vis[MAXN]; int pre[MAXN]; int mp[MAXN][MAXN]; bool bfs(int s,int t) { queue <int> que; ms(vis,0); ms(pre,-1); que.push(s); vis[s]=true; pre[s]=s; while(!que.empty()) { int u=que.front(); que.pop(); for(int i=1;i<=n;i++) { if(mp[u][i]&&!vis[i]) { vis[i]=true; pre[i]=u; if(i==t) return true; que.push(i); } } } return false; } int EK() { int ans=0; while(bfs(s,t)) { int mi=MAX_INT; for(int i=t;i!=s;i=pre[i]) { mi=min(mi,mp[pre[i]][i]); } for(int i=t;i!=s;i=pre[i]) { mp[pre[i]][i]-=mi; mp[i][pre[i]]+=mi; } ans+=mi; } return ans; } int main() { scanf("%d%d",&n,&m); scanf("%d%d",&s,&t); ms(mp,0); for(int i=1;i<=m;i++) { int x,y,z; scanf("%d%d%d",&x,&y,&z); mp[x][y]=z; } printf("%d\n",EK()); return 0; } /* 6 7 1 6 1 2 2 1 3 1 3 4 1 2 5 1 2 4 2 4 6 2 5 6 1 */ ``` 邻接表实现 ```cpp #include <queue> #include <cstdio> #include <cstring> #include <iostream> #define ms(n,x) memset(n,x,sizeof(n)) using namespace std; struct Edge { int to,next,weigh; }; struct Node { int from,id; }; const int MAXN = 10005; const int MAXM = 100005*2; const int MAX_INT = (1<<30); Edge edge[MAXM]; Node pre[MAXM]; int head[MAXM]; bool vis[MAXM]; int n,m,s,t,cont; void init() { cont=0; ms(edge,0); ms(head,-1); } void addedge(int from,int to,int weigh) { edge[cont].to=to; edge[cont].weigh=weigh; edge[cont].next=head[from]; head[from]=cont++; } bool bfs(int s,int t) { queue<int> que; ms(pre,-1); ms(vis,0); pre[s].from=s; vis[s]=true; que.push(s); while(!que.empty()) { int u=que.front(); que.pop(); for(int i=head[u];i+1;i=edge[i].next) { int from=edge[i].to; if(!vis[from]&&edge[i].weigh) { pre[from].from=u; vis[from]=true; pre[from].id=i; if(from==t) return true; que.push(from); } } } return false; } int EK() { int ans=0; while(bfs(s,t)) { int mi=MAX_INT; for(int i=t;i!=s;i=pre[i].from) { mi=min(mi,edge[pre[i].id].weigh); } for(int i=t;i!=s;i=pre[i].from) { edge[pre[i].id].weigh-=mi; edge[pre[i].id^1].weigh+=mi; } ans += mi; } return ans; } int main() { scanf("%d%d",&n,&m); scanf("%d%d",&s,&t); init(); for(int i=1;i<=m;i++) { int x,y,z; scanf("%d%d%d",&x,&y,&z); addedge(x,y,z); addedge(y,x,0); } printf("%d\n",EK()); return 0; } ``` 模板由此理解： https://blog.csdn.net/txl199106/article/details/64441994