SGU 194 无源无汇可行流求解

题意：n个点，m条边，每条边有容量限制 l--c，每个点满足容量平衡（流入等于流出），求可行解

无源无汇可行流问题，建立以一个超级源点和超级汇点，由于原来最大流问题时候，流量下界其实为0，

所以要转化，把边（设u-->v）的容量改为c-l，但是这样不平衡了，所以S流入v点l,u点流出到T要l，这样

保证了u,v流量平衡，用数组sumin[i]记录下i点流入下限之和，最后超级源点流入i。

最后求一次s-->t的最大流（走一遍dinic），如果添加的边都满流，说明有解（此时每条边所用流量+下限即可），

反之无解（必需要满流，否则不遵循流量平衡条件！）。（无源无汇模型和参考黑书

p366）。

#include<iostream>   //15ms

#include<cstdio>

#include<vector>

#include<queue>

using namespace std;

int n,m;const int inf=0x3f3f3f3f;

int e[90000][5];int head[210];  //链前星存边，0:to,1:pre,2,残量;3：l(下界);4,c

int sum_in[210];int sum_out[210];  //点i流入之和，流出之和

int vis[210];int level[210];

bool bfs()                     //dinic,小心细节！要熟练

{

    for(int i=0;i<=n+1;i++)

       vis[i]=level[i]=0;

    queue<int>q;q.push(0);vis[0]=1;

    while(!q.empty())

    {

        int cur=q.front();q.pop();

        for(int i=head[cur];i!=-1;i=e[i][1])

        {

            int v=e[i][0];

            if(!vis[v]&&e[i][2]>0)

            {

                level[v]=level[cur]+1;

                if(v==n+1)return 1;

                vis[v]=1;

                q.push(v);

            }

        }

    }

    return vis[n+1];

}

int dfs(int u,int minf)

{

    if(u==n+1||minf==0){return minf;}

    int sumf=0,f;

    for(int i=head[u];i!=-1&&minf;i=e[i][1])

    {   int v=e[i][0];

        if(level[v]==level[u]+1&&e[i][2]>0)

        {

            f=dfs(v,minf<e[i][2]?minf:e[i][2]);

            if(f<=0)continue;

            e[i][2]-=f;e[i^1][2]+=f;

            sumf+=f;minf-=f;

        }

    }

    return sumf;

}

void dinic()

{   int sumflow=0;

    while(bfs())

    {

        sumflow+=dfs(0,inf);

    }

}

bool check()                  //判断有无解

{

    for(int i=head[0];i!=-1;i=e[i][1])   //所有从超级源点出来的流量必满，否则无解！

        if(e[i][2]!=0)return 0;          //满必然有解，无需再判断汇点是否满（重复了）

   //   int v=n;                         //起初多此一举判断汇点满流情况，但是要注意一点

   // for(int i=head[n+1];i!=-1;i=e[i][1])  //边遍历顺序，前向星是前一条边，按添加时顺序相反

   //     if(e[i][2]!=sum_out[v--])return 0;//添加迟，出现早。

    return 1;

}

int main()

{

    while(~scanf("%d%d",&n,&m))

    {

        for(int i=0;i<=n+1;i++)

           {

               head[i]=-1;

               sum_in[i]=sum_out[i]=0;

           }

        int a,b,l,c;  int nume=0;

        for( ;nume<2*m;)                //读入，用每条边e[i][2]流量是残量，其他无用，只是保存起来，输出时用一下

        {

            scanf("%d%d%d%d",&a,&b,&l,&c);

            e[nume][0]=b;e[nume][1]=head[a];head[a]=nume;

            e[nume][4]=c;e[nume][3]=l;e[nume++][2]=c-l;

            sum_in[b]+=l;sum_out[a]+=l;

            e[nume][0]=a;e[nume][1]=head[b];head[b]=nume;

            e[nume++][2]=0;

        }

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

        {

            e[nume][0]=i;e[nume][1]=head[0];head[0]=nume;

            e[nume++][2]=sum_in[i];

            e[nume][0]=0;e[nume][1]=head[i];head[i]=nume;

            e[nume++][2]=0;

            e[nume][0]=n+1;e[nume][1]=head[i];head[i]=nume;

            e[nume++][2]=sum_out[i];

            e[nume][0]=i;e[nume][1]=head[n+1];head[n+1]=nume;

            e[nume++][2]=0;

        }

        dinic();

        if(!check())printf("NO\n");

        else

        {

            printf("YES\n");

            for(int i=0;i<2*m;i+=2)

            {

                printf("%d\n",e[i][4]-e[i][2]);

            }

        }

    }

    return 0;

}

巴特西

SGU 194 无源无汇可行流求解

最新文章

热门文章