hihocoder 1424 Asa’s Chess Problem(带上下界的最小费用可行流)

题目链接

发现貌似没白点的什么事。。。

那么我们可以把行和列视为2*n个初始点,从超级源向这些点连上下界均为初始黑点的流量,费用为0的边。因为这么多流量是一定流入这个点的。然后把pair视为边,因为我们只考虑黑点的转换,而且他们只在同一行或者同一列,所以当两个点在同一行,A点原来为黑色,所以我们就从A的初始点连向B的最终点一条流量为1费用为1的边。最终点向汇点连接带题目给的上下界的边。然后跑个上下界费用流。

记得要检查非法。。。

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注