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\n",ISAP());

    }

    return 0;

}

巴特西

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

最新文章

热门文章

巴特西

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

最新文章

热门文章

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