POJ 2112 Optimal Milking

題意：

    有K台機器以及C頭牛，每台機器能容納M頭牛，且點與點之間距離不一樣，現在要分配每頭牛到某台機器，某一隻牛走到機器路徑最遠，假設為D，現在要使得D値最小，並輸出D値。

    輸入第一行為K C M，接下來有(K+C)*(K+C)矩陣，表示這(K+C)個點之間的距離(如果無法到達則為0)。

想法：

    先用Floyd解出任兩點最短距離，然後用二分搜尋去找D値，每次二分就建立一個圖並做最大流，並判斷最後到達牛的數量是否為M，如果是則D値可以更小，如果不是則要把D値加大。

1. 建圖方法為將每頭牛i和每台機器j之間的距離如果<=D，也就是dis[i][j]<=D，那麼把i,j兩個點之間容量設為1(cap[i][j]=1)
2. 每頭牛與super source(S)相連，容量為1
3. 每台機器與super sink(T)相連，容量為M

	#include <cstdio>
	#include <queue>
	#include <cstring>
	#include <algorithm>
	using namespace std;
	#define INF 999999
	int K, C, M, N; // N = K + C
	int dis[500][500];
	int MaxFlow(int length);
	int cap[500][500], flow[500][500];
	int bottleneck[500], pre[500];
	int main()
	{
	scanf("%d %d %d", &K, &C, &M);
	N = K + C; // number of all nodes
	// Input
	for (int i = 0; i < N; ++i)
	for (int j = 0; j < N; ++j) {
	scanf("%d", &dis[i][j]);
	if (dis[i][j] == 0)
	dis[i][j] = INF;
	}
	// Floyd
	for (int k = 0; k < N; ++k)
	for (int i = 0; i < N; ++i)
	for (int j = 0; j < N; ++j)
	dis[i][j] = min(dis[i][j], dis[i][k]+dis[k][j]);
	// Binary Search
	int left = 1, mid, right = INF;
	while (left != right) {
	mid = (left + right) / 2;
	int sum = MaxFlow(mid);
	// check if all cows arrive
	if (sum >= C) right = mid;
	else left = mid + 1;
	}
	printf("%d\n", left);
	}
	int MaxFlow(int max_length)
	{
	// Initial
	int S = N, // Super source
	T = N+1; // Super sink
	memset(cap, 0, sizeof(cap));
	memset(flow, 0, sizeof(flow));
	for (int i = K; i < N; ++i) // 牛與機器之間距離<=max_length的容量設為1
	for (int j = 0; j < K; ++j)
	if (dis[i][j] <= max_length) cap[i][j] = 1;
	for (int i = 0; i < K; ++i) // for all machines
	cap[i][T] = M;
	for (int i = K; i < N; ++i) // for all cows
	cap[S][i]= 1;
	// BFS
	int result = 0;
	while (1) {
	memset(bottleneck, 0, sizeof(bottleneck));
	queue<int> Q;
	Q.push(S);
	bottleneck[S] = INF;
	while (!Q.empty() && !bottleneck[T]) {
	int cur = Q.front(); Q.pop();
	for (int nxt = 0; nxt < N+2; ++nxt) {
	if (bottleneck[nxt] == 0 && cap[cur][nxt] > flow[cur][nxt]) {
	Q.push(nxt);
	pre[nxt] = cur;
	bottleneck[nxt] = min(bottleneck[cur], cap[cur][nxt] - flow[cur][nxt]);
	}
	}
	}
	if (bottleneck[T] == 0) break;
	for (int cur = T; cur != S; cur = pre[cur]) {
	flow[pre[cur]][cur] += bottleneck[T];
	flow[cur][pre[cur]] -= bottleneck[T];
	}
	result += bottleneck[T];
	}
	return result;
	}

view raw [POJ] 2112 Optimal Milking.cpp hosted with ❤ by GitHub