SGU 305 — Exhibition
二分图匹配的囧题,不用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 winsty
program 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: array[1..nn]of link;
match: array[1..2, 1..nn*nn]of longint;
used: array[1..nn*nn]of boolean; //1..nn
cover: array[1..nn]of boolean;
procedure qsort(l, r: longint);
var
i, j, d, t: longint;
begin
i := l;
j := r;
d := c[(l+r) div 2];
repeat
while c[i] < d do inc(i);
while c[j] > d do dec(j);
if i <= j then begin
t := c[i];
c[i] := c[j];
c[j] := t;
inc(i);
dec(j);
end;
until i > j;
if l < j then qsort(l, j);
if i < r then qsort(i, r);
end;
function find(x: longint): longint;
var
l, r, d: longint;
begin
l := 1;
r := nc;
while true do begin
d := (l + r) div 2;
if c[d] = x then begin
find := d;
exit
end
else if c[d] > x then
r := d - 1
else
l := d + 1;
end;
end;
procedure addEdge(x, y: longint);
var
work: link;
begin
new(work);
work^.next := nil;
work^.v := y;
if head[x] = nil then begin
head[x] := work;
tail[x] := work;
end
else begin
tail[x]^.next := work;
tail[x] := work;
end;
end;
function search(x: longint): boolean;
var
work: link;
t1, t2, i: longint;
begin
if cover[x] then begin
search := false;
exit;
end;
cover[x] := true;
search := true;
work := head[x];
while work <> nil do begin
i := work^.v;
t1 := match[1, x];
t2 := match[2, i];
match[1, x] := i;
match[2, i] := x;
if t2 = 0 then exit;
match[1, x] := t1;
match[2, i] := t2;
work := work^.next;
end;
work := head[x];
while work <> nil do begin
i := work^.v;
t1 := match[1, x];
t2 := match[2, i];
match[1, x] := i;
match[2, i] := x;
if search(t2) then exit;
match[1, x] := t1;
match[2, i] := t2;
work := work^.next;
end;
search := false;
end;
begin
readln(n, m);
nc := 0;
for i:=1 to n do begin
readln(a[i], b[i]);
if a[i] > 0 then begin
if b[i] > 0 then
ts := - (b[i] - 1) div a[i]
else if b[i] = 0 then
ts := 1
else
ts := (- b[i]) div a[i] + 1;
end
else if a[i] = 0 then begin
if b[i] > 0 then begin
if b[i] > m then continue;
inc(nc);
c[nc] := b[i];
end;
continue;
end
else if a[i] < 0 then begin
if b[i] <= 0 then continue;
if b[i] - m - 1 >= 0 then
ts := (b[i] - m - 1) div (- a[i]) + 1
else
ts := 0;
end;
if ts < 0 then ts := 0;
for j:=ts to ts+n-1 do begin
if (a[i] * j + b[i] > m) or (a[i] * j + b[i] < 1) then break;
inc(nc);
c[nc] := a[i] * j + b[i];
end;
end;
if nc > 1 then begin
qsort(1, nc);
nt := nc;
nc := 1;
for i:=2 to nt do
if c[i] <> c[i-1] then begin
inc(nc);
c[nc] := c[i];
end;
end;
for i:=1 to n do begin
if a[i] > 0 then begin
if b[i] > 0 then
ts := - (b[i] - 1) div a[i]
else if b[i] = 0 then
ts := 1
else
ts := (- b[i]) div a[i] + 1;
end
else if a[i] = 0 then begin
if b[i] > 0 then begin
if b[i] > m then continue;
addEdge(i, find(b[i]));
end;
continue;
end
else if a[i] < 0 then begin
if b[i] <= 0 then continue;
if b[i] - m - 1 >= 0 then
ts := (b[i] - m - 1) div (- a[i]) + 1
else
ts := 0;
end;
if ts < 0 then ts := 0;
for j:=ts to ts+n-1 do begin
if (a[i] * j + b[i] > m) or (a[i] * j + b[i] < 1) then break;
addEdge(i, find(a[i]*j+b[i]));
end;
end;
fillchar(used, sizeof(used), false);
fillchar(match, sizeof(match), 0);
for i:=1 to n do begin
fillchar(cover, sizeof(cover), false);
if match[1, i] = 0 then
search(i);
end;
for i:=1 to n do
if (match[1, i] <> 0) and (c[match[1, i]] <= n*n) and (c[match[1, i]] >= 1) then
used[c[match[1, i]]] := true;
usep := 1;
for i:=1 to n do
if match[1, i] = 0 then begin
while used[usep] do inc(usep);
used[usep] := true;
write(usep, ‘ ‘);
end
else
write(c[match[1, i]], ‘ ‘);
end.
阅读(155 次)