本文主要是介绍POJ 2112 Optimal Milking (二分+匈牙利），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：在一片草场上有K台挤奶机，每台挤奶机最多可以为M头奶牛挤奶。有C头奶牛。把奶牛和挤奶机看做个体，则所有个体之间有一定的距离。现在给出K,C,M以及所有个体之间的距离。在保证所有奶牛都可以挤奶的情况下，求路程最长的奶牛的最小路程。
题解: 题目已经保证了所有奶牛都可以挤奶，那么最长的路径自然是 （顶点数-1） * 200。我们只需要二分最小路程，然后判断在此情况下是否所有的奶牛都存在合适的匹配。
#include <iostream>
using namespace std;#define MAX 250
#define INF 99999999
#define min(a,b) (a<b?a:b)int map[MAX][MAX];
int match[MAX][MAX]; // 每台机器可以为M头奶牛挤奶，所以应该用二维数组。当然也可以把机器拆点
bool vis[MAX];
int K, C, M, n;void floyed () // 求出两点间的最小距离
{int i, j, k;for ( k = 1; k <= n; k++ )for ( i = 1; i <= n; i++ )for ( j = 1; j <= n; j++ )map[i][j] = min ( map[i][j], map[i][k] + map[k][j] );
}bool find_path ( int u, int bin ) // bin为路程
{for ( int i = 1; i <= K; i++ ){if ( !vis[i] && map[u][i] <= bin ) // 路程<=bin {vis[i] = true;if ( match[i][0] < M ){match[i][++match[i][0]] = u;return true;}for ( int j = 1; j <= match[i][0]; j++ ){if ( find_path ( match[i][j], bin ) ){match[i][j] = u;return true;}}}}return false;
}bool Hungary ( int bin )
{memset(match,0,sizeof(match));for ( int i = K+1; i <= K+C; i++ ){memset(vis,0,sizeof(vis));if ( ! find_path ( i, bin ) ) return false; // 只要存在一头奶牛没有匹配上，则不成立}return true;
}int main()
{int i, j, l, r, mid;scanf("%d%d%d",&K,&C,&M);n = K+C;for ( i = 1; i <= n; i++ )for ( j = 1; j <= n; j++ ){scanf("%d",&map[i][j]);if ( !map[i][j] ) map[i][j] = INF;}l = 1; r = ( K + C ) * 200;floyed();while ( l < r ){mid = l + ( r - l ) / 2;if ( Hungary ( mid ) )r = mid;elsel = mid + 1;}printf("%d\n",r);return 0;
}
这篇关于POJ 2112 Optimal Milking (二分+匈牙利）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
