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 )