前辈有句话总结的好——最大值最小，最小值最大，十有八九是二分。Orz
那显然这题就是二分答案喽！

首先，枚举的下界就是1喽！为什么不会是0嘞？因为0在输入中代表的是没有边哦。
其次，枚举的上界就是Floyd之后的最大值喽！好麻烦啊，那就用200*(K+C)凑合一下吧。

然后，枚举了mid，怎么判断是否可行呢？
我们找来了网络流兄弟，请他帮帮忙吧。

对于原图，如果两点间距离>mid，那么这条路径就是不能走的；反之，就是能走的。
于是，对于一个枚举的mid，利用所有长度<=mid的路径构造网络流图，跑最大流。
具体构造方法：
超级源点向每个机器连一条容量为M的边，超级汇点向每只哞哞连一条容量为1的边。
然后，每个机器和每只哞哞之间，如果距离<=mid，就连一条容量为1的边。
如果最大流==牛的总数，那么就是可行的。
题意保证存在解使得所有哞哞都有机器，即 C<=K*M。

那么，上好的代码来了！

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
using namespace std;

/* POJ 2112 */

const int INF = 0x3f3f3f3f;
const int maxK = 35, maxC = 205, maxM = 20, maxV = 300;

int K, C, M, V;
int G[maxV][maxV];
int cap[maxV][maxV], dep[maxV], St, Ed;

inline void buildGraph(int limit) {

	/* prepare */
	memset(cap, 0, sizeof(cap));
	St = 0, Ed = V + 1;

	/* milkingMachines */
	for (int i = 1; i <= K; i++)
		cap[St][i] += M;

	/* cows */
	for (int i = K + 1; i <= V; i++)
		cap[i][Ed] += 1;

	/* cows and milingMachines */
	for (int i = 1; i <= K; i++)
		for (int j = K + 1; j <= V; j++)
			cap[i][j] += (G[i][j] <= limit);

}

inline bool dinicBFS(void) {

	/* prepare for BFS */
	memset(dep, -1, sizeof(dep));
	int que[maxV], head = 0, tail = 0;

	/* start of BFS */
	que[tail++] = St, dep[St] = 0;
	while (head != tail) {
		int u = que[head++];
		for (int v = 0; v <= Ed; v++)
			if (dep[v] == -1 && cap[u][v])
				dep[v] = dep[u] + 1, que[tail++] = v;
	}

	return dep[Ed] != -1;

}

inline int dinicDFS(int u, int f) {

	if (u == Ed)return f;

	int tmp = f, newFlow;
	for(int v=0;v<=Ed;v++)
		if (dep[v] == dep[u] + 1 && cap[u][v] > 0) {
			newFlow = dinicDFS(v, min(tmp, cap[u][v]));
			cap[u][v] -= newFlow;
			cap[v][u] += newFlow;
			tmp -= newFlow;
		}

	return f - tmp;

}

inline int dinic(void) {

	/* maxFlow */
	int maxFlow = 0;
	while (dinicBFS())
		maxFlow += dinicDFS(St, INF);

	return maxFlow;

}

inline bool check(int mid) {

	buildGraph(mid);
	int maxFlow = dinic();

	return maxFlow == C;

}

inline void Floyd(void) {

	/* FloydAlgorithm */
	for (int k = 1; k <= V; k++)
		for (int i = 1; i <= V; i++)
			for (int j = 1; j <= V; j++)
				G[i][j] = min(G[i][j], G[i][k] + G[k][j]);

}

signed main(void) {

#ifndef ONLINE_JUDGE
	printf(" POJ 2112 \n By YOUSIKI \n");
#endif

	/* input */
	scanf("%d%d%d", &K, &C, &M), V = K + C;
	for (int i = 1; i <= V; i++)
		for (int j = 1; j <= V; j++)
			scanf("%d", &G[i][j]);
	for (int i = 1; i <= V; i++)
		for (int j = 1; j <= V; j++)
			if (G[i][j] == 0)G[i][j] = INF;

	Floyd();

	/* binarySearch */
	int left = 1, right = V * 200, mid, ans = 1;
	while (left <= right) {
		mid = (left + right) >> 1;
		if (check(mid))right = mid - 1, ans = mid;
		else left = mid + 1;
	}

	/* output */
	printf("%d\n", ans);

#ifndef ONLINE_JUDGE
	system("pause");
#endif

}	// By YOUSIKI

• Re:牛哇牛哇 (0) 4324321 2022-03-21 10:45:32