POJ 2455 Secret Milking Machine

題意：
    有N個點(編號1~N)組成無向圖，總共有P條邊，要找出從編號1走到編號N共T條路徑(也就是有T條從1~N的路徑)，使得這T條路徑最長的那條為最小。假設T條中最長的那條路徑長為D，我們要找出D的最小値。
     輸入第一行分別為N P T，接下來有P行，每行u v d表示有一條u到v距離為d的邊，注意u到v可能會有很多條邊，且這T條路徑不能重邊。

想法：
    二分搜尋+最大流，用二分去找D値，每次二分時就重新建一個新的圖，建圖方法為假設dis[u][v]<=D，就把[u][v]容量+1，建完圖後做最大流並確認是否有T條路徑，如果有則D値可以再小，如果沒有則要把D値加大。

	#include <cstdio>
	#include <cstring>
	#include <queue>
	using namespace std;
	#define INF 999999999
	struct Edge{
	int u,
	v,
	len;
	}E[40001];
	int cap[205][205], flow[205][205];
	int bottleneck[205], pre[205];
	int MaxFlow(int length, int N, int P);
	int main()
	{
	int N, P, T;
	scanf("%d %d %d", &N, &P, &T);
	// Input
	int u, v, c, max_edge = 0;
	for (int i = 0; i < P; ++i) {
	scanf("%d %d %d", &E[i].u, &E[i].v, &E[i].len);
	max_edge = max(max_edge, E[i].len);
	}
	// Binary Search
	int left = 0, right = max_edge, mid;
	while (left != right) {
	mid = (left + right) / 2;
	if (MaxFlow(mid, N, P) >= T) right = mid;
	else left = mid + 1;
	}
	printf("%d\n", left);
	}
	int MaxFlow(int length, int N, int P)
	{
	// build graph
	memset(cap, 0, sizeof(cap));
	memset(flow, 0, sizeof(flow));
	for (int i = 0; i < P; ++i) {
	if (E[i].len <= length)
	cap[E[i].u][E[i].v] = (cap[E[i].v][E[i].u] += 1); // 用+=因為u到v可能不只一條道路
	}
	// bfs
	int result = 0;
	while (1) {
	memset(bottleneck, 0, sizeof(bottleneck));
	queue<int> Q;
	Q.push(1);
	bottleneck[1] = INF;
	while (!Q.empty() && !bottleneck[N]) { // 記得加!bottleneck[N]優化, 不然TLE
	int cur = Q.front(); Q.pop();
	for (int nxt = 1; nxt <= N; ++nxt) {
	if (bottleneck[nxt] == 0 && cap[cur][nxt] > flow[cur][nxt]) {
	pre[nxt] = cur;
	Q.push(nxt);
	bottleneck[nxt] = min(bottleneck[cur], cap[cur][nxt] - flow[cur][nxt]);
	}
	}
	}
	if (bottleneck[N] == 0) break;
	for (int cur = N; cur != 1; cur = pre[cur]) {
	flow[pre[cur]][cur] += bottleneck[N];
	flow[cur][pre[cur]] -= bottleneck[N];
	}
	result += bottleneck[N];
	}
	return result;
	}

view raw [POJ] 2455 Secret Milking Machine.cpp hosted with ❤ by GitHub