最大流模板(Dinic, ISAP)

最大流模板(Dinic, ISAP)

经过XPC同学的实验，目前得出的结论有：

1. 加上各种强优化的Dinic算法稍快于ISAP。

2. 在各种不同类型数据的对比测试下(如二分图VS层次较深的图，稠密图VS稀疏图，正向建图VS逆向建图)，Dinic算法要比ISAP稳定(这个结论尚待实证，不可全信)。

3. Dinic算法的优化有：当前弧优化、多路增广优化、-1优化。

4. 递归版Dinic已经够用，非递归版的Dinic要稍快于递归版的Dinic。

5. ISAP算法的优化有：GAP优化、多路增广优化，当前弧优化对ISAP算法无效。

6. 递归版ISAP已经够用，预处理出距离标号的ISAP稍快于无预处理的ISAP，但效率提升不明显，建议不采用。非递归版的ISAP效率提升不明显，建议不采用。

//Dinic 强优化
//模板题：BZOJ1838草地排水
//作者：XPC#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#define Min(a,b) (a<b?a:b)using namespace std;const int MAXN=10005, MAXM=20000005, INF=0x7f7f7f7f;int n, m, d[MAXN], cur[MAXN];
vector<int> Eid[MAXN];struct Edge {int c, v;
} E[MAXM];void AddEdge(int x, int y, int c)
{static int cnt=-1;E[++cnt].v=y, E[cnt].c=c;Eid[x].push_back(cnt);E[++cnt].v=x, E[cnt].c=0;Eid[y].push_back(cnt);
}bool BFS()
{static int Q[MAXN];int x, i, ql, qr;memset(d, -1, sizeof(d));Q[ql=qr=0]=1, d[1]=0;while (ql <= qr) {x = Q[ql++];for (i=0; i<Eid[x].size(); i++) {const Edge &e=E[Eid[x][i]];if (e.c && d[e.v]==-1) {Q[++qr] = e.v;d[e.v] = d[x]+1;if (e.v==n) return true;}}}return false;
}int Aug(int x, int a)
{if (x==n) return a;int aug=0, delta;for (int &i=cur[x]; i<Eid[x].size(); i++) {Edge &e=E[Eid[x][i]];if (e.c && d[e.v]==d[x]+1) {delta = Aug(e.v, Min(a,e.c));if (delta) {e.c -= delta;E[Eid[x][i]^1].c += delta;aug += delta;if (!(a-=delta)) break;}}}if (!aug) d[x]=-1;return aug;
}int MaxFlow()
{int flow=0;while (BFS()) {memset(cur, 0, sizeof(cur));flow += Aug(1,INF);}return flow;
}int main()
{scanf("%d%d", &m, &n);int x, y, c;while (m--) {scanf("%d%d%d", &x, &y, &c);AddEdge(x, y, c);}printf("%d", MaxFlow());return 0;
}

//ISAP 新写法 递归版 无当前弧优化
//模板题：BZOJ1838草地排水
//作者：XPC
#include <cstdio>
#include <vector>
#define Min(a,b) (a<b?a:b)using namespace std;const int MAXN=10005, MAXM=20000005, INF=0x7f7f7f7f;int n, m, d[MAXN], nd[MAXN];
vector<int> Eid[MAXN];struct Edge {int c, v;
} E[MAXM];void AddEdge(int x, int y, int c)
{static int cnt=-1;E[++cnt].v=y, E[cnt].c=c;Eid[x].push_back(cnt);E[++cnt].v=x, E[cnt].c=0;Eid[y].push_back(cnt);
}int Aug(int x, int a)
{if (x == n)return a;int i, id, delta, aug=0;for (i=0; i<Eid[x].size(); i++) {id = Eid[x][i];if (!E[id].c) continue;if (d[E[id].v] == d[x]-1) {delta = Aug(E[id].v, Min(a,E[id].c));if (delta) {E[id].c -= delta;E[id^1].c += delta;aug += delta;a -= delta;}else if (d[1]>=n || !a)return aug;}}if (!aug) {if (!--nd[d[x]]){d[1]=n; return 0;}int mi=n;for (i=0; i<Eid[x].size(); i++) if (E[id=Eid[x][i]].c)mi = Min(mi,d[E[id].v]);nd[d[x]=mi+1]++;}return aug;
}int MaxFlow()
{int flow=0;nd[0] = n;while (d[1] < n)flow += Aug(1,INF);return flow;
}int main()
{scanf("%d%d", &m, &n);int x, y, c;while (m--) {scanf("%d%d%d", &x, &y, &c);AddEdge(x, y, c);}printf("%d", MaxFlow());return 0;
}

/*
Name:	Templates_for_Test
Author:	FLanS39
Date:	2013/3/19
*/
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <ctime>
#include <algorithm>
#include <iostream>using namespace std;namespace {typedef unsigned uint;typedef long long lint;typedef unsigned long long ulint;//Windows, RAND_MAX=0x7fffint Rand16(){return (rand()<<1)|(rand()&1);}uint Rand32(){return (Rand16()<<16)|Rand16();}ulint Rand64(){return (ulint(Rand32())<<32)|Rand32();}int Rand(int L, int R){return Rand32()%(R-L+1)+L;}lint Rand64(lint L, lint R){return Rand64()%(R-L+1)+L;}double fRand(double L, double R){return double(Rand32())/uint(-1)*(R-L)+L;}double GetTime(clock_t begin, clock_t end){return double(end-begin)/CLOCKS_PER_SEC;}
};int main()
{srand(time(0));int n, m, i, cap=100000;scanf("%d%d", &n, &m);printf("%d %dn", m, n);for (i=n; i<=m; i++)printf("%d %d %dn", Rand(1,n), Rand(1,n), Rand(1,cap));for (i=1; i<n; i++)printf("%d %d %dn", i, i+1, Rand(1,cap));return 0;
}