Posted on 四月 6th, 2008.
第一次完成了KM的题目~撒花~
不过还是参考了好多次标程,后面要加强KM的熟练程度~
一定不能再出小毛病…比如把search := false;写做search := true;之类的…
题目第一行输入一个n,表示二分图左右结点分别有n个.
第二行n个数,第i个数xi表示左边第i个结点向右边结点连边时权值为xi^2.
后面n行,第i+2第一个数ki表示左边第i个结点向右边连边的条数,接下来ki个数表示向哪些结点连边.
很裸的KM,随便写写就可以.
附代码.
{
Beloved Sons; SGU 210
- sqybi’s code
- 最大匹配
- KM Kuhn-Munkres
}
//for my winsty
program sgu210_sqybi;
const
fin = ’sgu210.in’;
fout = ’sgu210.out’;
nn = 400;
var
i, j, m, n, x: longint;
b: array[1..nn, 1..nn]of longint;
vx, vy: array[1..nn]of boolean;
a, lx, ly: array[1..nn]of longint;
match: array[1..nn]of longint;
function search(x: longint): boolean;
[…]
Read Full Post |
Make a Comment ( 4 so far )
Posted on 四月 5th, 2008.
这道题算是十分经典的二分答案+二分图匹配了(怎么都是二分=.=…).
第一行读入一个n,后面n行每行n个数.要求选出n个数,任意两个不在同一行同一列,使它们的最大值最小.可能有经验的OIer看到”最大值最小”就知道了,这道题是二分答案.首先二分最大值x,然后对于所有最大值小于等于x的数在二分图里建边(这里把行和列看做二分图的两组结点,不用特意建边,只要判断一下就可以).接下来就是Hungary了.
刚开始写的有问题的一点是,没有看到二分时会有负数.后来更改之后AC.总体来说是比较简单的题目.P.S.Hungary练习的差不多了,准备开始写KM.另外开始用017899这个SGU的ID…有兴趣的去看看Information~
{Unstable Systems; sgu 218- sqybi’s code- 二分答案+Hungary}//for my winstyprogram sgu218_sqybi; const nn = 500;
var a: array[1..nn, 1..nn]of longint; match: array[1..2, 1..nn]of longint; visit: array[1..nn]of boolean; n, i, j, l, r, mid: longint;
function search(x, y: longint): boolean; var i, t1, t2: longint; begin search := false; if visit[x] then exit; visit[x] := […]
Read Full Post |
Make a Comment ( None so far )
Posted on 四月 2nd, 2008.
二分图匹配的囧题,不用HopCroft就能AC.其实必须用HopCroft的题目不多…
题目的意思大概就是,给你n组数,(a[i], b[i]),对于每组数要求你给定一个x[i](1<=x[i]<=m),使得有尽量多的(a[i], b[i], x[i])能够找到一个非负整数k,使得a[i]*k+b[i]=x[i].要求输出的是所有的x[i].
这道题呢,首先想到的是,对于每个(a[i], b[i]),作为二分图左侧的第i个点,向右侧的所有a[i]*k+b[i]连边.不过可以看到,m很大,a[i]和b[i]也很大,所以这种方法是不可行的.但是,再稍微想一下,就可以发现这个算法其实是可行的.因为左侧只有n个点,所以如果对于左侧第i个点,在右侧有多于n个可以连边的点,只需要连n条边就可以–因为其余n-1个点最多占用这n条边里的n-1条,这样第i个点一定可以找到一个匹配.
但是细节上还是有很多要注意的地方(这道题我交了接近10次才AC…).首先是连边的n个点的查找,这里最囧了.MaShuo的程序写的比我的简单的多,不过我不太明白他的写法…我这个写法其实还是很清晰的(当然我自己都看不懂).然后呢,有一种可能,就是左边的每个点都没有向右的连边,这时我的qsort就需要一个特殊判断,否则无法进行…注意按照我的写法,qsort(1, 0)是要RE的…最后,就是关于那个boolean数组(used数组).算法应该是先把所有能够匹配的点打上标记,然后每次找一个没有匹配的点,随便赋给一个没有用过的值,然后在boolean数组里给这个值也打上标记.注意我的boolean数组开到了n^2,其实没有必要,因为最多有n个点,所以对于任意一个没有匹配上的,1~n的值里一定有没用过的,随便给一个就可以了.
P.S.刚才Nxun看我的程序发现了一个关于那个used数组的错误,还以为自己AC了…高兴了半天…结果RE on Test 12…
{SGU 305; Exhibition- sqybi’s code- 二分图匹配; Hungary}//for my winstyprogram sgu305_sqybi; const nn = 300;
type link = ^obj1; obj1 = record v: longint; next: link; end;
var n, m, nc, nt, i, j, ts, usep: longint; a, b: array[1..nn]of int64; c: array[1..nn*nn]of longint; head, tail: […]
Read Full Post |
Make a Comment ( None so far )
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 )