SGU 218 — Unstable Systems
这道题算是十分经典的二分答案+二分图匹配了(怎么都是二分=.=…).
第一行读入一个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 winsty
program 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] := true;
search := true;
for i:=1 to n do
if a[x, i] <= y then begin
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;
end;
for i:=1 to n do
if a[x, i] <= y then begin
t1 := match[1, x];
t2 := match[2, i];
match[1, x] := i;
match[2, i] := x;
if search(t2, y) then exit;
match[1, x] := t1;
match[2, i] := t2;
end;
search := false;
end;
function check(x: longint): boolean;
var
i: longint;
begin
fillchar(match, sizeof(match), 0);
for i:=1 to n do
if match[1, i] = 0 then begin
fillchar(visit, sizeof(visit), false);
search(i, x);
end;
check := false;
for i:=1 to n do
if match[1, i] = 0 then
exit;
check := true;
end;
begin
readln(n);
r := -maxlongint;
l := maxlongint;
for i:=1 to n do begin
for j:=1 to n do begin
read(a[i, j]);
if a[i, j] > r then
r := a[i, j];
if a[i, j] < l then
l := a[i, j];
end;
readln;
end;
while l < r - 1 do begin
mid := (l + r) div 2;
if check(mid) then
r := mid
else
l := mid + 1;
end;
if not check(l) then begin
check(r);
writeln(r);
for i:=1 to n do
writeln(i, ‘ ‘, match[1, i]);
end
else begin
writeln(l);
for i:=1 to n do
writeln(i, ‘ ‘, match[1, i]);
end;
end.
阅读(123 次)