Poj 2112 Optimal Milking (多重匹配+传递闭包+二分)

题目链接：

题目描述：

　　有k个挤奶机，c头牛，每台挤奶机每天最多可以给m头奶牛挤奶。挤奶机编号从1到k，奶牛编号从k+1到k+c，给出(k+c)*(k+c)的矩阵maps，maps[i][j]代表i到j的距离，问到达挤奶机需要步行最长的奶牛最短要走多少距离？(刚开始看到题目很迷啊，怎么算测试实例答案都是1，原来是非真实存在的路径长度都记为0，那么maps中的零就是INF咯)。

解题思路：

　　因为要找出步行最长距离的奶牛最少走多远，每个奶牛到达挤奶机之前可以经过多条路径，所以我们要先进行一次floyd进行传递闭包，让maps[i][j]为i到j的最短路径。然后二分枚举奶牛的路径最大距离，每次用多重匹配判断是否合法即可。

 #include <cstdio>

 #include <cstring>

 #include <iostream>

 #include <algorithm>

 using namespace std;

 const int INF = 0x3f3f3f3f;

 const int maxn = ;

 int maps[maxn][maxn], used[][], link[], vis[];

 int mid, low, high, k, c, m;

 void floyd (int n)

 {

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

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

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

             {

                 maps[i][j] = min (maps[i][j], maps[i][k]+maps[k][j]);

                 high = max (maps[i][j], high);

                 low = min (low, maps[i][j]);

             }

 }

 bool Find (int x)

 {

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

     {

         if (!vis[i] && maps[x][i]<=mid)

         {

             vis[i] = ;

             if (link[i]<m)

             {

                 used[i][link[i] ++] = x;

                 return true;

             }

             for (int j=; j<m; j++)

                 if (Find(used[i][j]))

                 {

                     used[i][j] = x;

                     return true;

                 }

         }

     }

     return false;

 }

 bool hungry ()

 {

     memset (link, , sizeof(link));

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

     {

         memset (vis, , sizeof(vis));

         if (!Find(i))

             return false;

     }

     return true;

 }

 int main ()

 {

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

     {

         int n = k + c;

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

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

             {

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

                 if (maps[i][j] ==  && i!=j)

                     maps[i][j] = INF;

             }

         high = , low = INF;

         floyd (n);

         int ans;

         while (low <= high)

         {

             mid = (low+high)/;

             if (hungry())

             {

                 ans = mid;

                 high = mid - ;

             }

             else

                 low = mid + ;

         }

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

     }

     return ;

 }

巴特西

Poj 2112 Optimal Milking (多重匹配+传递闭包+二分)

最新文章

热门文章