题目名称	1632. 搬运工
输入输出	`worker.in/out`
难度等级	★★
时间限制	1000 ms (1 s)
内存限制	256 MiB
测试数据	10
题目来源	OI永别于2014-05-13加入
开放分组	全部用户
提交状态
分类标签	网络流
	分享题解

通过：35，提交：51，通过率：68.63%
AntiLeaf	100	0.000 s	0.00 MiB	C++
Shirry	100	0.000 s	0.00 MiB	C++
new ioer	100	0.004 s	1.38 MiB	C++
Hzoi_chairman	100	0.005 s	1.46 MiB	C++
RP++	100	0.005 s	1.47 MiB	C++
真呆菌	100	0.005 s	1.92 MiB	C++
Hzoi_chairman	100	0.008 s	1.31 MiB	C++
OI永别	100	0.008 s	1.54 MiB	C++
digital-T	100	0.009 s	0.33 MiB	C++
bbsh	100	0.009 s	1.54 MiB	C++

关于搬运工的近10条评论(全部评论)
好神啊 Shirry 2017-05-03 22:04 5楼
好神啊…… 真呆菌 2015-04-01 15:31 4楼
吐槽，内个不是他想的，吐槽=——= ◆半城烟沙灬為你打天下 2014-05-14 19:15 3楼
回复 @丿Nice丶蒙奇 : 太神了 , 2014-05-14 15:31 2楼
这是个很经典的二分图模型。以行为二分图的x部，列为二分图的y部。若格子(x, y)需要被消除，则连一条从x到y的边。最少次数即为二分图的最小点覆盖数。易证最小点覆盖数等于二分图的最大匹配数。　　但是题目还要求代价尽量小。那么怎么办呢？实际上，最大匹配也可以当做最小割做。从源s向每个x部点连一条容量为1的边，从每个y部点向汇t连一条容量为1的边，而二分图的每条边容量设为+∞。一个割会使得s和t不连通，也就使得二分图的每条边的两个端点中至少有一个被选出。同时最小割是所有割中代价最小的。　　提出这个模型的意义在于可以通过修改边的容量使得它能解决此题。我们考虑修改这个最小割模型的边的容量。将原来容量为1的边修改容量为10^6+ai(或bj)。由于数据范围中ai, bj<=100且n <= 100，所以∑ai+∑bj仍然远小于10^6。所以最小割必然是先满足删去的边尽量少，然后满足附加的容量和尽量小。　　最小次数即等于新图最小割除以10^6的商，最小代价等于最小割模10^6的余数。如果用Dinic计算最小割，则时间复杂度是O(n4)。实际上最短增广路算法一般远远达不到理论复杂度，因此可以完美地解决这道题。 OI永别 2014-05-13 18:50 1楼

1632. 搬运工

★★ 输入文件：worker.in 输出文件：worker.out 简单对比
时间限制：1 s 内存限制：256 MiB

【题目描述】

小涵向小宇推荐了一款小游戏。

游戏是这样的，在一个n*n的地图中，有若干个格子上有障碍物。你需要雇佣搬运工，将这些障碍物全部清除。不过每次操作你只能让搬运工将某一行或者某一列的障碍物全部清除。如果你让搬运工清除第i行障碍物，需要付出ai元；如果你让搬运工清除第j列障碍物，需要付出bj元。

小涵告诉小宇，必须用尽可能少的次数消除这些障碍物。若有多种方案，则必须花费尽量少的费用。结果小宇想了很久仍然没有闯过第一关，只好向你求助了。

【输入格式】

第1行，一个正整数n。

第2~n+1行，每行n个字符。第i+1行的第j个字符表示地图的坐标(i, j)的格子（左上角为起点(1, 1)）。’*’表示障碍，’.’表示空格。

第n+2行，n个正整数，第i个数表示清除地图第i行的费用。

第n+3行，n个正整数，第i个数表示清除地图第i列的费用。

【输出格式】

输出2行。第1行是最少次数，第2行是在最少次数的前提下费用的最小值。

【样例输入】

3
...
.*.
**.
10 5 17
1 8 4

【样例输出】

2
9

【提示】

30%的数据满足对于任意i和j(1 <= i, j <= n)，有ai = bj。

100%的数据满足1 <= n <= 200，0 <= ai, bj <= 100.

[样例说明]一共有三个障碍物，坐标分别是(2, 2), (3, 1), (3, 2)。消除第1列和第2列是最优方案。

【来源】

HZOI