poj2112 二分+floyd+多源多汇最大流

/*此题不错，大致题意：c头牛去k个机器处喝奶，每个喝奶处最多容纳M头牛，求所有牛中走的最长路的

那头牛，使该最长路最小。思路：最大最小问题，第一灵感：二分答案check之。对于使最长路最短，

用folyd算出所有牛到每个喝奶点的最短路，每次枚举最大值，取不大于该值的路，重新构图；把所有牛赶去

喝奶点，在喝奶点有限制，不是多源多汇吗？！取超级源点，限制为1（一头牛），超级汇点，限制为

m,即可。其他路限制随意。

关键点：分清哪些是流量，最短路只是构图的一个方式（条件）。此题注意编号（原图1--k是目标，后面是

牛（起点）。）

#include<iostream>   //140ms, 1A

#include<cstdio>

#include<vector>

#include<queue>

using namespace std;

int k,c,m;const int inf =0x3f3f3f3f;

int a[250][250]; int minmax;

int e[20000][3];int head[250];  //链式前向星二维数组表示法，0：to,1:pre,2:wight;

void folyd()       //最短路不用说

{

     for(int i=1;i<=k+c;i++)

       for(int j=1;j<=k+c;j++)

         for(int ii=1;ii<=k+c;ii++)

            {

                if(a[j][ii]>a[j][i]+a[i][ii])

                {

                    a[j][ii]=a[j][i]+a[i][ii];

                  if(a[j][ii]>minmax)minmax=a[j][ii];  //枚举上界

                }

            }

}

void build(int limit)  //由限制，选小于之的路，重新构图

{

    for(int i=0;i<=k+c+2;i++)

        head[i]=-1;

       int num=0;

     for(int i=c+1;i<=c+k;i++)   //超级汇点

     {

         e[num][0]=c+k+1;e[num][1]=head[i];head[i]=num;

         e[num++][2]=m;

         e[num][0]=i;e[num][1]=head[c+k+1];head[c+k+1]=num;

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

     }

      for(int i=1;i<=c;i++)  //超级源点

     {

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

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

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

         e[num++][2]=1;

     }

     for(int i=1;i<=k;i++)  //其他点

        for(int j=k+1;j<=k+c;j++)

           if(a[i][j]<=limit)

             {

                 e[num][0]=j-k;e[num][1]=head[i+c];head[i+c]=num;

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

                 e[num][0]=i+c;e[num][1]=head[j-k];head[j-k]=num;

                 e[num++][2]=1;

             }

}

int level[250];int vis[250];

bool bfs()                        //bfs+dfs,dinic算法

{

    for(int i=0;i<=k+c+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 to=e[i][0];

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

              {

                  vis[to]=1;

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

                  if(to==k+c+1)return 1;

                  q.push(to);

              }

          }

    }

    return vis[k+c+1];

}

int dfs(int uu,int minf)

{

    if(uu==k+c+1||minf==0)return minf;

    int sum=0,f;

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

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

              if(level[to]==level[uu]+1&&e[i][2]>0)

              {

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

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

                  sum+=f;minf-=f;

              }

          }

      return sum;

}

bool check(int limit)

{

    build(limit);

    int sumflow=0;

    while(bfs())

    {

        sumflow+=dfs(0,inf);

    }

    if(sumflow==c)   //所有牛可以去才是对

      return 1;

   return 0;

}

int main()

{

    scanf("%d%d%d",&k,&c,&m);

    for(int i=1;i<=k+c;i++)

       for(int j=1;j<=k+c;j++)

        {

            int temp1;

            scanf("%d",&temp1);

            if(temp1==0)a[i][j]=inf;

            else a[i][j]=temp1;

        }

      folyd();

      int left=0,right=minmax,mid;

      while(right>left+1)      //二分答案，注意一下

      {

          mid=(right+left)/2;

          if(check(mid))

          {

              right=mid;

          }

          else

            left=mid;

      }

      if(check(right-1))    //最后二分时判断特殊情况

      printf("%d\n",right-1);

      else

        printf("%d\n",right);

}

巴特西

poj2112 二分+floyd+多源多汇最大流

最新文章

热门文章