本文共 8996 字，大约阅读时间需要 29 分钟。
转载请注明出处：http://blog.csdn.net/sprintfwater/article/details/7913181
Dinic算法Accepted 1532 15MS 280K 2468 B C++ SpringWater可能是数据比较水吧，居然和sap算法一个时间效率,这个算法算是最差的了。当然相对与DFS来说还是要强得多这个算法的基本思想：每次求可达路径都根据刚分好层的图，从src一层层的递增找到des，之后有一次分层，又深搜。没有gap优化，cur优化，和没有利用insert来避免每次都分层（即当前弧优化）。总结者：SpringWater(GHQ)#include#include #define mafromn 222 #define MAXN 222 #define MAXE 500000 const int inf = 0x3f3f3f3f; struct edge{ int from,to,next; int c;}edge[MAXE]; int cnt,head[MAXN],stack[MAXN],dep[MAXN]; void add(int from,int to,int c) { edge[cnt].from=from;edge[cnt].to=to;edge[cnt].c=c; edge[cnt].next=head[from];head[from]=cnt++; edge[cnt].from=to;edge[cnt].to=from;edge[cnt].c=0; edge[cnt].next=head[to];head[to]=cnt++; } int flow(int n,int src,int des) { int tr,res=0; int i,j,k,f,r,top; while(1){ memset(dep,-1,n*sizeof(int)); for(f=dep[stack[0]=src]=0,r=1;f!=r;) { for(i=stack[f++],j=head[i];j!=-1;j=edge[j].next) { if(edge[j].c&&-1==dep[k=edge[j].to]){ dep[k]=dep[i]+1;stack[r++]=k; if(k==des) { f=r; break; } } } } if(dep[des]==-1)break; for(i=src,top=0;;) { if(i==des) { for(k=0,tr=inf;k
SAP和ISAP算法的效率差不多： 总结者：SpringWater(GHQ) #include#include #define MAXN 100010 #define MAXE 400010 const int INF = 0x3f3f3f3f; struct Edge { int to, from, next, cap; }edge[MAXE]; int head[MAXN],cnt,n,m,src,des; int dep[MAXN], gap[MAXN]; //dep[des] = 0初始化为0，代表汇点des的深度为0，gap[0] = 1代表深度为0的点有1个，即汇点 void addedge(int cu, int cv, int cw) { edge[cnt].from = cu; edge[cnt].to = cv; edge[cnt].cap = cw; edge[cnt].next = head[cu]; head[cu] = cnt++; edge[cnt].from = cv; edge[cnt].to = cu; edge[cnt].cap = 0; edge[cnt].next = head[cv]; head[cv] = cnt++; } int que[MAXN]; void BFS() { memset(dep, -1, sizeof(dep)); memset(gap, 0, sizeof(gap)); gap[0] = 1; int L = 0, R = 0; dep[des] = 0; que[R++] = des; int u, v; while (L != R) //用光搜的方法，从汇点开始，将此图分层。 { u = que[L++]; L = L%MAXN; for (int i=head[u]; i!=-1; i=edge[i].next) { v = edge[i].to; if (edge[i ^1].cap == 0 || dep[v] != -1) //i^1代表i的反向边,edge[i ^1].cap == 0代表v点到u点不可答 continue; que[R++] = v; //如果v点可达，则加入队列 R = R % MAXN; ++gap[dep[v] = dep[u] + 1]; //v的深度，等于u的深度+1，且深度为dep[v]的点的个数加1 } } } int cur[MAXN],stack[MAXN]; int Sap() //sap模板 { int res = 0; BFS(); int top = 0; memcpy(cur, head, sizeof(head)); //将每个点的第一条边复制给cur，以便于后面找深度u点小1的边不用从头开始找 int u = src, i; while (dep[src] < n) //如果src找不到一个可达点，则dep[src] = n + 1自动退出 { if (u == des) //当找到汇点 { int temp = INF, inser = n; for (i=0; i!=top; ++i){ //找从src点到des点的所有边中的最容量为temp,而那条边的编号为insert if (temp > edge[stack[i]].cap){ temp = edge[stack[i]].cap; inser = i; } } for (i=0; i!=top; ++i) //将正向边-temp，反向变+temp { edge[stack[i]].cap -= temp; edge[stack[i]^1].cap += temp; } res += temp; //总的流量加temp top = inser; //stack只保留从src到最小边insert“前向点”之间的边的信息，即insert边以后的边信息都不要 u = edge[stack[top]].from; //u为insert的”前向点“ } for (i = cur[u]; i != -1; i = edge[i].next) //当没有断层，找出一个可达边 if (edge[i].cap != 0 && dep[u] == dep[edge[i].to] + 1) break; if (i != -1) //当找到这个可达边 { cur[u] = i; //优化下次找dep[u] - 1不用从头开始找了 stack[top++] = i; u = edge[i].to; } else //当没有找到深度为dep[u] - 1的可达边，那只能找深度更大的边 { /*因为在不断的增广过程中，每个点的dep只会增，不会减，深度比u小1的点已经没有了， 即深度大于等于dep[u]的点过不了，dep[u] - 1这层，而ISAP算法就不能这样优化，因为 它是将所有的点初始化为0，所以大于0的 而这道题把这句话扔掉反而时间还边少了0ms； 不过令人奇怪的是，这题在在去掉这个优化的时候时间反而还从0ms变为了15ms*/ if (--gap[dep[u]] == 0) break; int minn = n; //从头开始找出深度最小的可达边 for (i = head[u]; i != -1; i = edge[i].next) { if (edge[i].cap == 0) continue; if (minn > dep[edge[i].to]) { minn = dep[edge[i].to]; cur[u] = i; //优化避免从头找 } } ++gap[dep[u] = minn + 1]; if (u != src) //如果u不是源点，还得回溯到dep[u] + 1（这里的dep[u]！=minn + 1）层，并将dep[u]层点全部修改变大。一直回溯到源点 u = edge[stack[--top]].from; } } return res; } int main() { while (~scanf("%d%d", &m, &n)) { src = 0;//源点为0 des = n - 1;//汇点为n-1 cnt = 0; memset(head, -1, sizeof(head)); int u, v, c; for (int i =0; i < m; ++i) { scanf("%d%d%d", &u, &v, &c); --u, --v;//输入是从1点开始，而src是从0点开始 addedge(u,v,c); // addedge(v,u,c); //流量为双向，如果是单向得去掉这句 } int ans = Sap(); printf("%d\n", ans); } return 0; }
//题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1532ISAP算法：Accepted 1532 0MS 444K 3014 B C++ SpringWater初步实验这个算法最优：基本思想是将所有点的深度都初始化为0，在增广的过程中就自动分层。再直接利用SAP算法增广即可，相对与SAP算法相比，只是代码简短一些，其他也占不了什么优势。总结者：SpringWater(GHQ)ps：这个代码是我自己敲的。终于敲网络流有种轻车熟路的感觉。#include#include #include #include using namespace std; #define MAXN 10005 #define MAXE 200000 #define INF 1e9 int tmp,src,des,cnt;int n,m; struct Edge{ int from, to; int next,cap; }edge[MAXE]; int head[MAXN]; int gap[MAXN],dep[MAXN],cur[MAXN], stack[MAXN], top;int ISAP() { int cur_fLow,max_fLow,u,insert,i; memset(dep,0,sizeof(dep)); memset(gap,0,sizeof(gap)); memcpy(cur, head, n); max_fLow = 0; u = src; top = 0; while(dep[src] < n) { if(u == des) { cur_fLow = INF; for(i = 0; i < top; ++i) { if(cur_fLow > edge[stack[i]].cap) { insert = i; cur_fLow = edge[stack[i]].cap; } } for(i = 0; i < top; ++i) { edge[stack[i]].cap -= cur_fLow; edge[stack[i]^1].cap += cur_fLow; } max_fLow += cur_fLow; u = edge[ stack[top = insert]].from; } for(i = cur[u]; i != -1; i = edge[i].next) if((edge[i].cap > 0) && (dep[u] == dep[edge[i].to]+1)) break; if(i != -1) { stack[top++] = i; u = edge[i].to; } else { if(0 == --gap[dep[u]]) break; int minn = n; for(i = head[u]; i != -1; i = edge[i].next) { if(edge[i].cap > 0) minn = (minn > dep[edge[i].to]) ? (cur[u]= i, dep[edge[i].to]) : minn; } ++gap[dep[u] = minn + 1]; if(u != src) u = edge[stack[--top]].from; } } return max_fLow; } void addedge(int u,int v,int f) { edge[cnt].next = head[u]; edge[cnt].from = u; edge[cnt].to = v; edge[cnt].cap = f; head[u] = cnt++; edge[cnt].next = head[v]; edge[cnt].from = v; edge[cnt].to = u; edge[cnt].cap = 0; head[v] = cnt++; } int main(){ while(scanf("%d%d",&m,&n)!=EOF) { cnt=0; src = 0; des = n-1; memset(head,-1,sizeof(head)); while(m--) { int a, b, c; scanf("%d%d%d", &a, &b, &c); --a, --b; addedge(a, b, c); //addedge(b, a, c);如果是无向边的加上这句 } int ans=ISAP(); printf("%d\n",ans); } return 0; }