others

HNOI模拟赛 — news

Posted on 三月 28th, 2008.

这道题我也不知道是哪儿的题…说是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: [...]

Read Full Post | Make a Comment ( None so far )

superbt — 超级bt的题目

Posted on 三月 22nd, 2008.

这道题简直把平衡树的BT程度发挥到了极致…
上次写WA了,这次先是WA,然后RE201,然后RE215(这个东西…最后确认是某个节点的father是它自己,然后不断的把size增大…就溢出了),最后AC.还有比较囧的,我的程序一度无法编译…后来发现是因为数组开的太大,到了几百M.似乎object里面的这个错误检查不出?
这道题其实也很简单了,题目描述都不用发,注释里都写的很清楚了…不过考到了平衡树的所有操作.里面删除大于等于k的所有数,似乎Splay最简单…然后还有Treap据说也可以和Splay一样做,别的平衡树都要一个一个删.我这个程序就是Splay的…效率不错.
虽然AC了也很恶心…因为用了object…所以400+行…不过object在那些并查集+平衡树啊,线段树套平衡树啊,还有我一直没做的线段树+LCA之类的题目中还是挺有用的,至少过程不会混淆了.
{ superbt - sqybi’s code - Splay - delete出错:   “if son[1, y] <> 0 then father[son[1, y]] := z;”   写作   “if son[1, y] <> 0 then father[son[1, y]] := son[1, z];”}{$APPTYPE CONSOLE}//for my winstyprogram superbt_sqybi;  const    fin = ’superbt.in’;    fout = ’superbt.out’;    nn = 10000000;    unable = 100000000;
  type    TSplayTree = object      private        root, [...]

Read Full Post | Make a Comment ( 8 so far )