Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

二分答案+网络流判断可行性,附AC代码

Posted by yousiki at 2016-07-30 20:31:08 on Problem 2112
前辈有句话总结的好——最大值最小,最小值最大,十有八九是二分。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

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator