poj 1719 Shooting Contest (匈牙利算法)

2016年5月30日 0 作者 CrazyKK

poj1719题目链接

题意:射箭比赛,靶子是一个n*m的网格。网格的特点是没列只有两个白色,剩下的全是黑色。一共射m次,每列射一次,要求每行都射到至少一次才算合法,问是否有合法射法,如果有输出一组解。

思路:由于列数可能比行数多,那么我们把行编号作为左集合,列编号作为右集合,做一次匈牙利,对于每一行都找到它匹配的列,如果匹配数等于n,说明有解。对于输出一组街的问题,m列中已经匹配了n列,输出他们对应的link即可。对于剩下的m-n列,可以任意输出。由于之前不知道会剩下哪n-m列,所以在读入的时候有必要保存每一列的white格子的位置信息。

1A,有点爽。