poj 2391 Ombrophobic Bovines 二分+拆点+floyd+最大流

缘起

综合题做起来就是舒服~ poj 2391 Ombrophobic Bovines

分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
有F块田地，已知每块田地上面牛的数量和雨篷能遮蔽的牛的数量；有P条路无向边连接任意两块田地，每条路有固定的耗
费时间。问如果下雨了，所有的牛要怎么走，才能使得在最短的时间（最后的牛进入雨篷算迁移完成）内让所有的牛进
入雨篷，如果不能的话输出-1。如果能的话, 输出最短时间。

【输入】
第一行，F和P（1 <= F <= 200， 1 <= P <= 1500）, 然后是F行，每行2个数字, 第一个数字是这块低的牛的
数量([0,1000]).第二个数字是这块地的雨棚能容纳的牛的数量（[0,1000]）.
然后是P行，每行三个整数，描述2个地之间的耗费时间（时间范围是[1,1,000,000,000]）。

【输出】
所有牛都进入雨棚的最短时间,办不到的话输出-1

【样例输入】
3 4
7 2
0 4
2 6
1 2 40
3 2 70
2 3 90
1 3 120

【样例输出】
110

【限制】
1s

本题的做法是二分答案——因为 答案具备单调性.

将每块地拆点成两个流网络的点. 第一个点是此地的牛群，第二个点是此地的雨棚. 则建立炒鸡源和炒鸡汇. 炒鸡源到牛群的弧容量显然就是牛群的牛的数量. 而雨棚到炒鸡汇的弧的容量显然就是雨棚能容纳的牛的数量. 然后本地的牛群可以选择不出走. 所以连接当地牛群和雨棚之间的弧（容量为inf）

关键就是一个地方的牛群到另一个地方的雨棚的弧怎么连接？

首先，floyd预处理出任何2块不同地之间的最短路径（注意，就算有重边, 我们伊始只取耗时最短的那一条即可）. 然后 对于地i和第j, 如果i和j之间的最短时间>二分答案的t的话, 则不连弧. 否则连inf容量的弧.

这样, 流网络就建好了. 在上面跑最大流算法即可. 注意, 本题我们采用【1】中最后说的那种方式构图（即）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
//#include "stdafx.h"
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <queue>
using namespace std;
//#define LOCAL
typedef long long LL;
const LL inf = ~0ull>>4, maxn = 205;

LL f,p,t, head[maxn<<1], rhead[maxn<<1],rcap[maxn*maxn<<1], cnt,rcnt, gg[maxn][maxn], tot1, tot2, ub, pre[maxn<<1], flow[maxn<<1]; // gg是最短路网络,跑floyd算法的, tot1是牛的总数, tot2是雨棚能容纳的牛的总数, ub是二分答案的上界

struct Arc
{
	LL from,to,nxt,cap;
}g[maxn*maxn<<1]; // 牛和雨棚之间两两连弧不超过maxn*maxn, 然后反向弧*2, g是流网络,跑最大流算法的

void addArc(LL from, LL to, LL cap)
{
	g[cnt].from = from, g[cnt].to = to, g[cnt].nxt = head[from], g[cnt].cap = cap;
	head[from] = cnt++;
	g[cnt].from = to, g[cnt].to = from, g[cnt].nxt = head[to], g[cnt].cap = 0;
	head[to] = cnt++;
}

void floyd()
{
	for (LL k = 1; k<=f; k++)
	{
		for (LL i = 1; i<=f; i++)
		{
			for (LL j = 1; j<=f; j++)
			{
				gg[i][j] = min(gg[i][j],gg[i][k]+gg[k][j] );
			}
		}
	}
}

void build(LL x)
{
	for (LL i = 1; i<=f; i++)
	{
		for (LL j = i+1; j<=f; j++)
		{
			if (gg[i][j]<=x)
			{
				addArc(i,f+j,inf);
				addArc(j, i+f, inf); // i和j处都有牛和雨棚哦~
			}
		}
	}
}

void updata(LL s, LL t, LL d)
{
	LL h;
	while(t!=s)
	{
		h = pre[t];
		g[h].cap-=d;
		g[h^1].cap+=d;
		t = g[h].from;
	}
}

LL bfs(LL s, LL t)
{
	queue<LL> q;
	q.push(s);
	memset(pre, -1, sizeof(pre));
	flow[s] = inf;
	while(!q.empty())
	{
		LL front = q.front();
		q.pop();
		if (front==t)
		{
			updata(s,t,flow[t]);
			return flow[t];
		}
		for (LL h = head[front],to; ~h; h = g[h].nxt)
		{
			to = g[h].to;
			if (!~pre[to] && g[h].cap>0)
			{
				pre[to] = h;
				flow[to] = min(flow[front], g[h].cap);
				q.push(to);
			}
		}
	}
	return 0;
}

LL ek(LL s,LL t)
{
	LL ans = 0;
	while(1)
	{
		LL d = bfs(s,t);
		if (!d)
		{
			return ans;
		}
		ans+=d;
	}
}

bool ck(LL x) // 检验x时限可以吗?
{
	build(x); // 根据时限x继续完成流网络的构图
	return ek(0,t)==tot1; // 看看是否满流. 如果满流的话, 说明所有牛都可以在时限x内找到雨棚避雨
}

void revover() // 恢复网络
{
	cnt = rcnt;
	for (LL i = 0; i<cnt; i++)
	{
		g[i].cap = rcap[i];
	}
	memcpy(head, rhead, sizeof(head)); 
}

LL kk() // 二分答案
{
	LL lo = 0, hi = ub, mid, ans = -1;
	while(lo<=hi)
	{
		mid = lo+hi>>1;
		if (ck(mid))
		{
			ans = mid;
			hi = mid-1;
		}
		else
		{
			lo = mid+1;
		}
		revover(); // 恢复网络
	}
	return ans;
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	//	freopen("d:\\my.out", "w", stdout);
#endif
	scanf("%lld%lld", &f, &p);
	memset(head, -1, sizeof(head));
	t = 2*f+1; // 炒鸡汇
	for(LL i = 1,a,b; i<=f; i++)
	{
		scanf("%lld%lld", &a, &b);
		tot1+=a, tot2+=b;
		if (a)
		{
			addArc(0, i, a);
		}
		if (b)
		{
			addArc(f+i, t, b);
		}
		addArc(i,f+i, inf); // 牛可以选择不走
	}
	rcnt = cnt; // 备份下没有加牛群到雨棚的弧的时候流网络弧的数量
	memcpy(rhead, head, sizeof(head)); // 备份一下
	for (LL i = 0; i<cnt; i++)
	{
		rcap[i] = g[i].cap;
	} // 备份一下容量
	if (tot1>tot2)
	{
		puts("-1"); // 如果牛的总数大于雨棚能容纳的牛的数量的话, 则显然不可能办到
		return 0;
	}
	for (LL i = 1;i<=f; i++)
	{
		for (LL j = i; j<=f; j++)
		{
			gg[i][j]=gg[j][i] = i==j?0:inf;
		}
	}
	for (LL i = 1,a,b,c; i<=p; i++)
	{
		scanf("%lld%lld%lld", &a, &b, &c); // a<-->b耗时c
		gg[a][b] = gg[b][a] = min(gg[a][b], c); // 注意, 这里考虑到了重边——只取最小的
	}  // 初始化gg
	floyd(); // gg上跑floyd
	for (LL i = 1; i<=f; i++)
	{
		for (LL j = 1; j<=f; j++)
		{
			if (gg[i][j]<inf)
			{
				ub = max(ub, gg[i][j]);
			}
		}
	} // 得到两块地之间的最近的最远距离了
	printf("%lld\n", kk());
	return 0;
}

但是遗憾的是，被T掉了. 但是我找到了全部测试数据, 跑出来的结果都是正确的. 所以应该是最大流的EK算法效率不够高导致的

遂寻找更加高效的最大流算法. 找到了 sap（shortest augmant path 最短增广路径算法）.

后面我会继续写文章来a掉这道题的. 毕竟SAP是一个比较大的头. 也是比较主流的最大流算法.