编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

匈牙利+二分...

程序WS了些

我坚持不cheat~

所以不能秒杀~

25\26 ACer

美妙的匈牙利有着美妙的应用

Orz 陶文博神牛！！！！！！！！！

构图是如果i+j(ij,然后求最小覆盖(有向无环)

第一个想法是枚举ans,求最小覆盖,发现匈牙利要超

接下来优化,发现匈牙利算法只是对每个点检查他是否能匹配点,所以每次只需要查询没有被匹配的点是否能匹配就OK.

注意放入的顺序必须是从1~N。

此句话应该改成"注意放入的顺序必须是从1~Ans。"

宋氏图表?百度上只能找到一群家谱啊~~

//*知道最小路径覆盖以后，只要判断一下是否小于等于ans即可。 *//

ans应改成n

学了最小路径覆盖 ，可喜可贺

我是枚举上去的结果花了72ms....

Accepted 有效得分：100 有效耗时：0ms

我用宋氏图表0ms AC了！！！！！！！！！！！

宋神牛太强了！！！！！！！！！！！！！！！

打表

在N次80分之后，我终于发现：

素数表开小了！！！！

Orz 陶文博

oRZ楼下陶文博神牛!

这题是余姚中学7月14号模拟赛第四题

傻×水题。我这种神牛就直接写题解了，懒得写代码了。

首先，二分答案（答案在1到700之间，二分一下就行了）。

下面要解决对于给定答案ans，是否存在合法方案。

很容易想到，建一张这样的图：把1到ans作为节点，然后如果ij

比如样例：

4

3 7

2 6

1 5

那么这两根汉诺塔的放法就对应了图中的两条路径：

1->2->3->4

5->6->7

于是，问题转化为一张图，至少需要用多少条不相交路径才能将它盖住。

这个问题很简单，我们构建一张二分图：

二分图的x部和y部都是(1到ans，一共ans个点)

如果在原图存在边i->j,那么二分图中就对应了一条边 ： x部的i -> y部的j

对这张二分图求最大匹配即可，最小路径覆盖就是 点数-最大匹配数。

知道最小路径覆盖以后，只要判断一下是否小于等于ans即可。

全vijos最难一题?!?

Orz 陶文博神牛！！！！！！！！！1

什么东西？

Ubuntu

顶楼下陶文博神牛！！！

sf..