这题的大意是有C只牛，K台机器，C只牛与K台机器的距离是已知的，现在还知道，K台机器的最多能容下M只牛，现在问说如何安排这些牛到这些机器上，使得符合上述的限制，同时要使牛与机器的最远距离最小。具体的做法是二分答案，然后用二分匹配来判可行，可以修改下匈牙利匹配，也可以拆点后用直接的二分匹配，或者用复杂度高点的最大流。
代码 #include < iostream > #include < string > using namespace std; const int MAXK = 35 ; const int MAXC = 205 ; const int MAXM = 20 ; const int INF = 1000000 ; int K, C, M; int n, m; int mm[MAXK + MAXC][MAXK + MAXC]; bool d[MAXC][MAXK * MAXM]; int s[MAXK * MAXM]; int clo[MAXK * MAXM]; void floyd(){ for ( int k = 0 ; k < C + K; k ++ ) { for ( int i = 0 ; i < C + K; i ++ ) { for ( int j = 0 ; j < C + K; j ++ ) { if (mm[i][k] + mm[k][j] < mm[i][j]) mm[i][j] = mm[i][k] + mm[k][j]; } } }} void make_map( int limit){ for ( int i = 0 ; i < C; i ++ ) { for ( int j = 0 ; j < K; j ++ ) { if (mm[K + i][j] <= limit) d[i][j] = true ; else d[i][j] = false ; for ( int k = 0 ; k < M; k ++ ) { d[i][j + k * K] = d[i][j]; } } }} bool dfs( int i){ for ( int j = 0 ; j < m; j ++ ) { if (d[i][j] && s[j] == 0 ) { s[j] = 1 ; if (clo[j] == - 1 || dfs(clo[j])) { clo[j] = i; return true ; } } } return false ;} bool can( int limit){ make_map(limit); memset(clo, - 1 , sizeof (clo)); for ( int i = 0 ; i < n; i ++ ) { memset(s, 0 , sizeof (s)); if ( ! dfs(i)) return false ; } return true ;} int go(){ n = C; m = M * K; floyd(); int low = 1 , high = 20000 ; while (low <= high) { int mid = (low + high) / 2 ; if (can(mid)) high = mid - 1 ; else low = mid + 1 ; } return low;} int main(){ while (scanf( " %d%d%d " , & K, & C, & M) != EOF) { for ( int i = 0 ; i < K + C; i ++ ) { for ( int j = 0 ; j < K + C; j ++ ) { scanf( " %d " , & mm[i][j]); if (mm[i][j] == 0 ) mm[i][j] = INF; } } printf( " %d\n " , go()); }}
转载于:https://www.cnblogs.com/litstrong/archive/2010/09/22/1833198.html
相关资源：数据结构—成绩单生成器