isap算法模板poj 1273gap+弧优化 最大流

几个比较好的博客
http://www.renfei.org/blog/isap.html
http://kenby.iteye.com/blog/945454
http://blog.csdn.net/mypsq/article/details/37959249

#include<stdio.h>
#include<string.h>
#include<queue>
using namespace std;
#define inf 999999
#define N  300
struct node {
int u,v,w,next;
}bian[N*N*2];
int head[N],yong,stac[N],top,start,n,cur[N],dis[N],gap[N];
void init() {
memset(head,-1,sizeof(head));
memset(dis,-1,sizeof(dis));
memset(gap,0,sizeof(gap));
memset(cur,0,sizeof(cur));
top=0;start=1;yong=0;
}
void addedge(int u,int v,int w) {/*建边*/
    bian[yong].u=u;
    bian[yong].v=v;
    bian[yong].w=w;
    bian[yong].next=head[u];
    head[u]=yong++;
}
void bfs() {
queue<int>q;
q.push(n);
dis[n]=0;
int i;
/*建立层次图*/
while(!q.empty()) {
    int c=q.front();
    q.pop();
    for(i=head[c];i!=-1;i=bian[i].next) {
            int v=bian[i].v;
        if(dis[v]==-1) {//这里注意不能加这个条件(bian[i^1].w)
            dis[v]=dis[c]+1;
            q.push(v);
        }
    }
}
}
int ISAP() {
 int  k,i,sum=0;
 bfs();
for(i=1;i<=n;i++)//cur数组记录当前位置的边的坐标
    cur[i]=head[i];
 for(i=1;i<=n;i++)
    gap[dis[i]]++;//gap优化记录到汇点距离为dis[i]的个数
    k=start;
 while(dis[start]<n) {
    if(k==n) {//如果满足条件
            int mi=inf,index;
        for(i=0;i<top;i++)
        if(mi>bian[stac[i]].w) {//找最小流
            mi=bian[stac[i]].w;
            index=i;
        }
        for(i=0;i<top;i++) {//修改残留网络
            bian[stac[i]].w-=mi;
            bian[stac[i]^1].w+=mi;
        }
        sum+=mi;
        top=index;//定位到最小的边的权值的位置
        k=bian[stac[top]].u;//当前的k
    }
    for(i=cur[k];i!=-1;i=bian[i].next) {//遍历未走过的边
     int v=bian[i].v;
        if(bian[i].w&&dis[k]==dis[v]+1) {//
            cur[k]=i;
            k=v;
            stac[top++]=i;
            break;
        }
    }
    if(i==-1) {/*更新*/
        int m=n;
        for(i=head[k];i!=-1;i=bian[i].next)
            if(bian[i].w&&m>dis[bian[i].v]){
            m=dis[bian[i].v];
            cur[k]=i;//记录当前的边的下标
            }
        if(--gap[dis[k]]==0)break;//出现断层
        dis[k]=m+1;gap[dis[k]]++;
        if(k!=start)//如果非源点的话
            k=bian[stac[--top]].u;//退点，推到上一个点，将当前边删掉，因为是<top
    }
 }
 return sum;
}
int main() {
    int m,i,j,k;
    while(scanf("%d%d",&m,&n)!=EOF) {
        init();
        while(m--) {
            scanf("%d%d%d",&i,&j,&k);
            addedge(i,j,k);
            addedge(j,i,0);
        }
        printf("%d
",ISAP());
    }
    return 0;
}