二分图最大匹配 – Tgotp-Blog

1191: [HNOI2006]超级英雄Hero

二分图匹配裸题。

对于每道题看能否匹配,不行就跳出

洛谷还要输出方案数

c++代码如下:

 

1854: [Scoi2010]游戏

二分图最大匹配

由权值向点连边。跑一遍匈牙利就好了

c++代码如下:

 

4950: [Wf2017]Mission Improbable

对于俯视图观察发现:

零的位置必须为零,其余不用管。

即尽量把有东西的偷到1.

观察正视图:
发现对于答案有影响的只有每行最大值。

观察侧视图得到同样的结论。

于是乎先尽可能的取,留下每行每列的最大值。

然后如果有行列的最大值相同明显可以多取,跑一边二分图最大匹[……]

Read more