本文主要是介绍POJ 2289 Jamie's Contact Groups （二分+匹配/网络流），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：把n个点，分到m个组中。题目给出每一个点可以被分到的那些组。要求分配完毕后，最大的那一个组的人数最小。
题解：比较怪。一开始化作费用流做。假设每一次增广过后，路径上所有边的费用增大相等的值，这样一来，被增广过的路径下一次就不会被立即增广了。这样就能使与汇点相连的那些点均匀增加。结果悲剧TLE```。
#include <iostream>
using namespace std;#define MAX 1001
#define INF 999999999
#define min(a,b) (a<b?a:b)int match[MAX][MAX];
int group[MAX], cnt[MAX];
bool map[MAX][MAX];
bool vis[MAX];
int n, m;bool find_path ( int u )
{for ( int i = 1; i <= m; i++ ){if ( ! vis[i] && map[u][i] ){vis[i] = true;if ( match[i][0] < group[i] ){match[i][++match[i][0]] = u;return true;}for ( int j = 1; j <= match[i][0]; j++ )if ( find_path ( match[i][j] ) ){match[i][j] = u;return true;}}}return false;
}bool Hungary ()
{memset(match,0,sizeof(match));for ( int i = 1; i <= n; i++ ){memset(vis,0,sizeof(vis));if ( ! find_path ( i ) )return false;}return true;
}bool check ( int cap )
{for ( int i = 1; i <= m; i++ )group[i] = min ( cap, cnt[i] );return Hungary ();
}int main()
{int l, r, mid, g, i;char name[20];while ( scanf("%d%d",&n,&m) && ( n || m ) ){memset(map,0,sizeof(map));memset(cnt,0,sizeof(cnt));for ( i = 1; i <= n; i++ ){scanf("%s",name);while ( true ){scanf("%d",&g);cnt[g+1]++;map[i][g+1] = true;if ( getchar() == '\n' ) break;}}l = 0; r = 1001;while ( l < r ){mid = l + ( r - l ) / 2;if ( check ( mid ) )r = mid;elsel = mid + 1;}printf("%d\n",r);}//system("pause");return 0;
}这篇关于POJ 2289 Jamie's Contact Groups （二分+匹配/网络流）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
