网络流 POJ2112

题意：K个产奶机，C头奶牛，每个产奶机最多可供M头奶牛使用；并告诉了产奶机、奶牛之间的两两距离Dij(0<=i,j<K+C)。

问题：如何安排使得在任何一头奶牛都有自己产奶机的条件下，奶牛到产奶机的最远距离最短？最短是多少？

建图源点 -> 每头牛 -> 每个机器 -> 汇点

权 1 ? M

二分找最远距离里面最小的

二分距离 if dis[i][j]<dis 牛到机器的流量 1 也就是权

 #include<stdio.h>

 #include<algorithm>

 #include<string.h>

 #include<queue>

 using namespace std;

 #define MAXN 300

 #define inf  100000000

 int k,c,m,n;

 int S,T;                  //我把源点和汇点 设成 0 n+1

 int dis[MAXN][MAXN];

 int z[MAXN][MAXN];

 int vis[MAXN];

 void floyed()

 {

     int i,j,k;

     for(k=;k<=n;k++)

     {

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

         {

             for(j=;j<=n;j++)

             {

                 if(dis[i][j]>dis[i][k]+dis[k][j])

                     dis[i][j]=dis[i][k]+dis[k][j];

             }

         }

     }

 }

 void makemap(int w)

 {

     int i,j;

     memset(z,,sizeof(z));  //反向边这边已经有了

     for(i=k+;i<=n;i++)

         z[][i]=;

     for(i=;i<=k;i++)

         z[i][n+]=m;

     for(i=k+;i<=n;i++)

         for(j=;j<=k;j++)

         {

             if(dis[i][j]<=w)

                 z[i][j]=;

         }

 }

 int bfs()

 {

     memset(vis,-,sizeof(vis));

     vis[S]=;

     queue<int>q1;

     q1.push(S);

     int i;

     while(!q1.empty())

     {

         int now=q1.front();

         q1.pop();

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

         {

             if(vis[i]<&&z[now][i])

             {

                 q1.push(i);

                 vis[i]=vis[now]+;

             }

         }

     }

     return vis[T]!=-;

 }

 int dfs(int u,int w)

 {

     int ans=;

     if(u==T)

         return w;

     int i;

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

     {

         if(vis[i]==vis[u]+&&z[u][i])

         {

             int b=dfs(i,min(z[u][i],w-ans));

             z[u][i]-=b;

             z[i][u]+=b;

             ans=ans+b;

         }

     }

     return ans;

 }

 int main()

 {

     while(scanf("%d%d%d",&k,&c,&m)!=EOF)

     {

         int i,j;

         n=k+c;

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

             for(j=;j<=n;j++)

             {

                 scanf("%d",&dis[i][j]);

                 if(dis[i][j]==)

                     dis[i][j]=inf;

             }

         floyed();

         int L,R;

         L=;

         R=inf;

         S=;

         T=n+;

         int ans=;

         while(L<=R)

         {

             int w=,mid;

             mid=(L+R)>>;

             makemap(mid);

             while(bfs())

                 w+=dfs(,inf);

             if(w>=c)

             {

                 ans=mid;

                 R=mid-;

             }

             else

                 L=mid+;

         }

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

     }

     return ;

 }

巴特西

网络流 POJ2112

最新文章

热门文章