poj1459多源多汇最大流问题

/*基本构图题，多源多汇，添加一个源点和一个汇点，所有源点都来自这个源点，同理，所有汇点

都汇于这个汇点，dinic第二战，本来应该1A的，犯了一个低级错误！while(scanf("%d))要加“~”啊！

SB了，记住这个教训！此次顺带学习了scanf的又一读入，忽略空格和已有符号，不错，并且更加了解了

dinic算法（为什么要添加反向弧？反向弧其实是提供悔棋的机会（每次回走相当于原来的流量又回来了（直接把容量看成剩余的流量），二，这题本身有反向弧，直接叠加即可，若走原图反向弧，相当于走这条路，走添加的反向弧，相当于反悔））。

但是为什么我的dinic要900MS啊！*/

未1A原因：while（scanf...）！！~~~~~！！！

#include<iostream>  //900MS

#include<cstdio>

#include<vector>

#include<queue>

using namespace std;

int n,np,nc,m;

const int inf=0x3f3f3f3f;

struct edge

{

    int to,flow,pre;

};

edge e[24000];int head[120];

int vis[120],level[120];

bool bfs()

{

    for(int i=0;i<=n+3;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].pre)

        {

            int v=e[i].to;

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

            {

             vis[v]=1;

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

             if(v==n+1)return 1;       //优化之一

             q.push(v);

            }

        }

    }

    return vis[n+1];

}

int dfs(int u,int minf)    //minf 是目前为止残量

{

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

    int nowsumflow=0,zhihouflow;

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

        {

            int v=e[i].to;int temp=e[i].flow;

              if(level[v]==level[u]+1&&temp>0)

              {

                zhihouflow=dfs(v,minf<temp?minf:temp);

                if(zhihouflow==0)continue;

                e[i].flow-=zhihouflow;

                e[i^1].flow+=zhihouflow;

                nowsumflow+=zhihouflow;

                minf-=zhihouflow;

              }

        }

        return nowsumflow;

}

int main()

{

    while(~scanf("%d%d%d%d",&n,&np,&nc,&m))   //没有加~！跪了N久

    {

        int s,l,f;int i,j;

        for(int ii=0;ii<=n+4;ii++)

           head[ii]=-1;

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

        {

            scanf(" (%d,%d)%d",&s,&l,&f);

            if(s==l){i++;continue;}

            e[i].to=l+1;e[i].pre=head[s+1];

            head[s+1]=i;e[i].flow=f;

            i++;

            e[i].to=s+1;e[i].pre=head[l+1];

            head[l+1]=i;e[i].flow=0;

        }

        for(j=i;j<2*np+i;j++)

        {

            scanf(" (%d)%d",&s,&f);

            e[j].to=s+1;e[j].pre=head[0];

            head[0]=j;e[j].flow=f;

            j++;

            e[j].to=0;e[j].pre=head[s+1];

            head[s+1]=j;e[j].flow=0;

        }

         for(int k=j;k<2*nc+j;k++)

        {

            scanf(" (%d)%d",&s,&f);

            e[k].to=n+1;e[k].pre=head[s+1];

            head[s+1]=k;e[k].flow=f;

            k++;

            e[k].to=s+1;e[k].pre=head[n+1];

            head[n+1]=k;e[k].flow=0;

        }

        long long sumcom=0;

        while(bfs())

        {

            sumcom+=dfs(0,inf);

        }

        printf("%lld\n",sumcom);

    }

    return 0;

}

巴特西

poj1459多源多汇最大流问题

最新文章

热门文章