hdu 3879 最大权闭合图（裸题）

/*

裸的最大权闭合图

解：参见胡波涛的《最小割模型在信息学竞赛中的应用

#include<stdio.h>

#include<string.h>

#include<stdlib.h>

#include<queue>

using namespace std;

#define N  55100//刚开始开的是5100一直越界应该是n+m

#define NN  510000

#define inf 0x3fffffff

struct node {

int u,v,w,next;

}bian[NN*8];

int head[N],yong,dis[N],work[N];

void init() {

yong=0;

memset(head,-1,sizeof(head));

}

void addedge(int u,int v,int w) {

bian[yong].v=v;

bian[yong].w=w;

bian[yong].next=head[u];

head[u]=yong++;

}

int bfs(int s,int t)

{

    memset(dis,-1,sizeof(dis));

    queue<int>q;

    q.push(s);

    dis[s]=0;

    while(!q.empty())

    {

        int u=q.front();

        q.pop();

        for(int i=head[u];i!=-1;i=bian[i].next)

        {

            int v=bian[i].v;

            if(bian[i].w&&dis[v]==-1)

            {

                dis[v]=dis[u]+1;

                q.push(v);

                if(v==t)

                    return 1;

            }

        }

    }

    return 0;

}

int dfs(int  s,int limit,int t)

{

    if(s==t)return limit;

    for(int &i=work[s];i!=-1;i=bian[i].next)

    {

        int v=bian[i].v;

        if(bian[i].w&&dis[v]==dis[s]+1)

        {

            int tt=dfs(v,min(limit,bian[i].w),t);

            if(tt)

            {

                bian[i].w-=tt;

                bian[i^1].w+=tt;

                return tt;

            }

        }

    }

    return 0;

}

int dinic(int s,int t)

{

    int ans=0;

    while(bfs(s,t))

    {

        memcpy(work,head,sizeof(head));

        while(int tt=dfs(s,inf,t))

            ans+=tt;

    }

    return ans;

}

int main(){

    int n,m,i,k,sum,u,v,w,s,t;

    while(scanf("%d%d",&n,&m)!=EOF) {

        init();

        s=0;t=n+m+1;

        for(i=1;i<=n;i++) {

            scanf("%d",&k);

           addedge(i,t,k);

           addedge(t,i,0);

        }

        sum=0;

        for(i=1;i<=m;i++) {

            scanf("%d%d%d",&u,&v,&w);

            addedge(s,i+n,w);

            addedge(i+n,s,0);

            addedge(i+n,u,inf);

            addedge(u,i+n,0);

            addedge(i+n,v,inf);

            addedge(v,i+n,0);

            sum+=w;

        }

        printf("%d\n",sum-dinic(s,t));

    }

return 0;}

巴特西

hdu 3879 最大权闭合图（裸题）

最新文章

热门文章