匈牙利算法 – Tgotp-Blog

4950: [Wf2017]Mission Improbable

对于俯视图观察发现:

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

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

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

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

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

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

Read more

1433: [ZJOI2009]假期的宿舍

匈牙利算法;

向认识的人的床连边就行了。

注意:要向自己连边。。。。。之前这里wa了。。。。

c++代码如下:

 

BZOJ1059 && Luogu1129: [ZJOI2007]矩阵游戏

 

1059: [ZJOI2007]矩阵游戏

Time Limit: 10 Sec  Memory Limit: 162 MB
Submit: 4813  Solved: 2299
[Submit][Status][Discuss]

Description

  小Q是一个非[……]

Read more

1466 Girls and Boys

Girls and Boys

Time Limit: 5000MS

Memory Limit: 10000K

Total Submissions: 12771

Accepted: 5689

Description

In the seco[……]

Read more

P3386 【模板】二分图匹配

用了两种算法来测试,

网络流用dinic实现:

本以为网络流可以完虐匈牙利。

可惜洛谷这题太气人,边数太多,以至于一开始我re的莫名其妙。

所以得出结论,边数多的时候用匈牙利,少的时候用网络流。

匈牙利 117ms

网络流 342ms

 

以[……]

Read more