HNOI模拟赛 — news
这道题我也不知道是哪儿的题…说是HNOI模拟赛是我从gen的fp.ini的路径推测出来的…
题目大概就是说,给你一个有向无环图,然后用数量最少的不相交简单路径覆盖每一个结点.第一行输入n,m,为结点和边数.接下来m行每行两个整数x,y,代表x->y的一条有向边.
这道题是经典的二分图匹配了.对于边x->y,建立(x,y)这条二分图中的边.然后做最大匹配,易证明最大匹配+路径条数=结点数,问题解决.
我这道题的算法是HopCroft,一个sqrt(n)*m的算法,也就是Hungary的优化.这里有个问题问知道这个算法的大牛,为什么HopCroft算法如果找最短增广路增广,速度反而没有找最长增广路增广快?按理说最短增广路应该快啊…也是HopCroft的标准做法啊…这是巧合还是什么呢…
P.S.cqf大牛竟然没听说过HopCroft…P.S.又是我喜欢的object…这次加上了指针,还不算乱…不过似乎加了object速度掉的很厉害.HopCroft也不是很难写.
{news- sqybi’s code- 二分图匹配- Hopcroft}//for my winstyprogram news_sqybi; const fin = ‘news.in’; fout = ‘news.out’; nn = 100000;
type link = ^obj1; obj1 = record v: longint; next: link; end; TBipartiteGraph = object private len: longint; head, tail: array[1..2, 1..nn]of link; dist, match: array[1..2, 1..nn]of longint; check: array[1..nn]of boolean; q: array[1..nn]of longint; function search(x: […]