首页 > 代码库 > 网络流模板
网络流模板
在这里我只放我的模板和一些我个人的“理解”。。
最大流测试题：usaco草地排水
EK：
时间复杂度：O(VE^2)
代码复杂度：最易
代码：
#include <cstdio>#include <cstring>#include <queue>using namespace std;#define CLR(a) memset(a, 0, sizeof(a))#define FOR(i,a,n) for(i=a;i<=n;++i)const int maxn = 205, oo = ~0u >> 1;int cap[maxn][maxn], ihead[maxn], inext[maxn<<2], iv[maxn<<2], cnt;int p[maxn];queue<int> q;int n, m;int min(const int& a, const int& b) { return a < b ? a : b; }int EK(int s, int t) { int u, v, i, flow = 0, aug; while(1) { CLR(p); q.push(s); while(!q.empty()) { u = q.front(); q.pop(); for(i = ihead[u]; i ; i = inext[i]) if(cap[u][iv[i]] > 0 && !p[iv[i]]) { p[iv[i]] = u; q.push(iv[i]); } } if(!p[t]) break; aug = oo; for(v = t; v != s; v = p[v]) aug = min(aug, cap[p[v]][v]); for(v = t; v != s; v = p[v]) cap[p[v]][v] -= aug, cap[v][p[v]] += aug; flow += aug; } return flow;}void add(int u, int v, int c) { inext[++cnt] = ihead[u]; ihead[u] = cnt; iv[cnt] = v; cap[u][v] += c; inext[++cnt] = ihead[v]; ihead[v] = cnt; iv[cnt] = u;}int main() { scanf("%d%d", &m, &n); int u, v, c; for(int i = 1; i <= m; ++i) { scanf("%d%d%d", &u, &v, &c); add(u, v, c); } printf("%d", EK(1, n)); return 0;}
Dinic:
时间复杂度：O(V^2E)
代码复杂度：较长但不易出错
PS：这是加了当前弧优化的
代码2（这份代码的cap是二维的）：
#include <cstdio>#include <cstring>#include <queue>using namespace std;#define CLR(a) memset(a, 0, sizeof(a))#define FOR(i,a,n) for(i=a;i<=n;++i)const int maxn=205, oo=~0u>>1, maxm=maxn<<2;int cap[maxn][maxn], ihead[maxn], inext[maxm], iv[maxm], cnt;int vis[maxn], d[maxn], cur[maxn];queue<int> q;int n, m, s, t;int min(const int& a, const int& b) { return a < b ? a : b; }bool BFS() { //建立层次图 CLR(vis); q.push(s); d[s]=0; vis[s]=1; //这里记住要加上vis[s]=1; int u, i; while(!q.empty()) { u=q.front(); q.pop(); for(i=ihead[u]; i; i=inext[i]) if(!vis[iv[i]] && cap[u][iv[i]]) { d[iv[i]]=d[u]+1; vis[iv[i]]=1; q.push(iv[i]); } } return vis[t];}int DFS(int u, int a) { if(u==t || !a) return a; int f, flow=0; for(int& i=cur[u]; i; i=inext[i]) if(d[u]+1==d[iv[i]] && (f=DFS(iv[i], min(a, cap[u][iv[i]])))>0 ) { //沿着层次图走，并且这是条增广路 flow+=f, a-=f, cap[u][iv[i]]-=f, cap[iv[i]][u]+=f;//a保存的是之前路径的最小，所以不一定是等于f，所以要减掉f if(!a) break; //说明不可能再有增广路，也就是说，前面断了。 } return flow;}int dinic() { int flow=0, i; while(BFS()) { FOR(i, 1, n) cur[i]=ihead[i]; flow+=DFS(s, oo); } return flow;}void add(int u, int v, int c) { inext[++cnt]=ihead[u]; ihead[u]=cnt; iv[cnt]=v; cap[u][v]+=c; inext[++cnt]=ihead[v]; ihead[v]=cnt; iv[cnt]=u;}int main() { scanf("%d%d", &m, &n); int u, v, c; for(int i=1; i<=m; ++i) { scanf("%d%d%d", &u, &v, &c); add(u, v, c); } s=1; t=n; printf("%d", dinic()); return 0;}
代码2（cap已改为1维，并做了相应更改）：
#include <cstdio>#include <cstring>#include <queue>using namespace std;#define CLR(a) memset(a, 0, sizeof(a))#define FOR(i,a,n) for(i=a;i<=n;++i)const int maxn=205, oo=~0u>>1, maxm=maxn<<2;int cap[maxm], ihead[maxn], inext[maxm], to[maxm], cnt=1; //听取wyl意见，从2开始编号int vis[maxn], d[maxn], cur[maxn];queue<int> q;int n, m, s, t;int min(const int& a, const int& b) { return a < b ? a : b; }bool BFS() { //建立层次图 CLR(vis); q.push(s); d[s]=0; vis[s]=1; //这里记住要加上vis[s]=1; int u, i; while(!q.empty()) { u=q.front(); q.pop(); for(i=ihead[u]; i; i=inext[i]) if(!vis[to[i]] && cap[i]) { d[to[i]]=d[u]+1; vis[to[i]]=1; q.push(to[i]); } } return vis[t];}int DFS(int u, int a) { if(u==t || !a) return a; int f, flow=0; for(int& i=cur[u]; i; i=inext[i]) if(d[u]+1==d[to[i]] && (f=DFS(to[i], min(a, cap[i])))>0 ) { //沿着层次图走，并且这是条增广路 flow+=f, a-=f, cap[i]-=f, cap[i^1]+=f;//a保存的是之前路径的最小，所以不一定是等于f，所以要减掉f if(!a) break; //说明不可能再有增广路，也就是说，前面断了。 } return flow;}int dinic() { int flow=0, i; while(BFS()) { FOR(i, 1, n) cur[i]=ihead[i]; flow+=DFS(s, oo); } return flow;}void add(int u, int v, int c) { inext[++cnt]=ihead[u]; ihead[u]=cnt; to[cnt]=v; cap[cnt]=c; inext[++cnt]=ihead[v]; ihead[v]=cnt; to[cnt]=u;}int main() { scanf("%d%d", &m, &n); int u, v, c, i; for(i=1; i<=m; ++i) { scanf("%d%d%d", &u, &v, &c); add(u, v, c); } s=1; t=n; printf("%d", dinic()); return 0;}
isap（国人都叫sap，其实百度一下有解释的）：
时间复杂度：O(V^2E)实际快多了，这是我将来用的算法
代码复杂度：短但细节太多，易错
PS：这是加了当前弧优化、gap优化的、暂无瓶颈优化 | 话说，调sap我都调怕了，有点恐惧症了。。
代码1（容量我还是用二维的存）：
#include <cstdio>#include <cstring>#include <queue>using namespace std;#define CC(a, c) memset(a, c, sizeof(a))#define FOR(i,a,n) for(i=a;i<=n;++i)const int maxn=205, oo=~0u>>1, maxm=maxn<<2;int cap[maxn][maxn], ihead[maxn], inext[maxm], iv[maxm], cnt;int p[maxn], d[maxn], cur[maxn], gap[maxn];int n, m, s, t;int min(const int& a, const int& b) { return a < b ? a : b; }int isap() { int flow=0, u, v, i, f=oo; CC(d, 0); CC(gap, 0); for(i=1; i<=n; ++i) cur[i]=ihead[i]; u=p[s]=s; gap[0]=n; //这里预处理很重要，第一个赋值给p[s]是因为后面会调用，第二个是因为没有单独的bfs来处理d数组才要这样设置，否则一两次循环就要跳出了 while(d[s]<n) { for(i=cur[u]; i; i=inext[i]) if(cap[u][iv[i]] && d[u]==d[iv[i]]+1) break; if(i) { cur[u]=i; v=iv[i]; f=min(f, cap[u][v]); p[v]=u; u=v; //这里记得将u重新赋值过，cur当前弧优化 if(v==t) { for(; v!=s; v=p[v]) cap[p[v]][v]-=f, cap[v][p[v]]+=f; u=s; flow+=f; f=oo; //将u退回远点，似乎有叫瓶颈优化的东西，到时候再说吧。记得将最小流f重置 } } else { if( !(--gap[d[u]]) ) break; //gap优化，即发现断层立即终止 d[u]=n; //当没有发现允许弧时，要重新设置 cur[u]=ihead[u]; //这里最坑，，，还是请大神帮忙调试出来的0 0，应该这里是瓶颈优化的地方 for(i=cur[u]; i; i=inext[i]) if(cap[u][iv[i]] && d[u]>d[iv[i]]+1) d[u]=d[iv[i]]+1; gap[d[u]]++; u=p[u]; } } return flow;}void add(int u, int v, int c) { inext[++cnt]=ihead[u]; ihead[u]=cnt; iv[cnt]=v; cap[u][v]+=c; inext[++cnt]=ihead[v]; ihead[v]=cnt; iv[cnt]=u;}int main() { scanf("%d%d", &m, &n); int u, v, c, i; for(i=1; i<=m; ++i) { scanf("%d%d%d", &u, &v, &c); add(u, v, c); } s=1; t=n; printf("%d", isap()); return 0;}
代码2（已改为1维并相应修改）：
#include <cstdio>#include <cstring>#include <queue>using namespace std;#define CC(a, c) memset(a, c, sizeof(a))#define FOR(i,a,n) for(i=a;i<=n;++i)const int maxn=205, oo=~0u>>1, maxm=maxn<<2;int cap[maxm], ihead[maxn], inext[maxm], to[maxm], from[maxm], cnt=1; //听取wyl意见，从2开始编号int p[maxn], d[maxn], cur[maxn], gap[maxn];int n, m, s, t;int min(const int& a, const int& b) { return a < b ? a : b; }int isap() { int flow=0, u, v, i, f=oo; CC(d, 0); CC(gap, 0); for(i=1; i<=n; ++i) cur[i]=ihead[i]; u=s; gap[0]=n; //这里预处理很重要，第一个赋值给p[s]是因为后面会调用，第二个是因为没有单独的bfs来处理d数组才要这样设置，否则一两次循环就要跳出了 while(d[s]<n) { for(i=cur[u]; i; i=inext[i]) if(cap[i] && d[u]==d[to[i]]+1) break; if(i) { cur[u]=i; v=to[i]; f=min(f, cap[i]); p[v]=i; u=v; //这里记得将u重新赋值过，cur当前弧优化 //这里注意，p要赋值成i if(v==t) { for(; v!=s; v=from[p[v]]) cap[p[v]]-=f, cap[p[v]^1]+=f; u=s; flow+=f; f=oo; //将u退回远点，似乎有叫瓶颈优化的东西，到时候再说吧。记得将最小流f重置 } } else { if( !(--gap[d[u]]) ) break; //gap优化，即发现断层立即终止 d[u]=n; //当没有发现允许弧时，要重新设置 cur[u]=ihead[u]; //这里最坑，，，还是请大神帮忙调试出来的0 0，应该这里是瓶颈优化的地方 for(i=cur[u]; i; i=inext[i]) if(cap[i] && d[u]>d[to[i]]+1) d[u]=d[to[i]]+1; gap[d[u]]++; if(u!=s) u=from[p[u]]; //这里要注意 } } return flow;}void add(int u, int v, int c) { inext[++cnt]=ihead[u]; ihead[u]=cnt; from[cnt]=u; to[cnt]=v; cap[cnt]=c; inext[++cnt]=ihead[v]; ihead[v]=cnt; from[cnt]=v; to[cnt]=u; cap[cnt]=0;}int main() { scanf("%d%d", &m, &n); int u, v, c, i; for(i=1; i<=m; ++i) { scanf("%d%d%d", &u, &v, &c); add(u, v, c); } s=1; t=n; printf("%d", isap()); return 0;}
我自己的瞎扯：
网络流为什么要有反向弧：
最直观的是= =，如果自己原来的弧的点被其它的s-t占掉了，还可以通过反向弧从占掉那个点的弧（u，v）中的u流回去，去占它的点，从而构成一条新的s-tisap的Gap优化的解释：
断层这个概念，可以这样想：
b
/
a -- c
\
d
这里我们假设d(a)=5
此时假设b后的增广路已经完了，那么d(b) = n，但是我们发现，还有d(c)=4，即没有断层。
一直下去，直到d(c)和d(d)都为n了，此时没有一个d(i)=4，所以，发生断层，此时d(i)=4的数目为0，所以就可以结束程序了。
这就是所谓的Gap优化～网络流这一类题的初始化：
首先就要将所有点和该连的弧给连了，否则容易出错，什么拆点啊这些操作首先搞掉。
网络流上下界的胡扯解释：
为什么一条边(u,v)的的下界是从附加源连到v呢？
我是这样认为的： 从源开始流，又流回了u，再流回汇，如果满了，就能判断了0.0
同理，将u连到了汇上。。而汇到源连一条无限容量的弧是为了让那个下界流从这里流回去。。
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。