HNOI模拟赛 — news
这道题我也不知道是哪儿的题…说是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 winsty
program 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: longint): boolean;
public
procedure init;
procedure addEdge(x, y: longint);
function maxMatch: longint;
end;
var
n, m, i, x, y: longint;
bip: TBipartiteGraph;
function TBipartiteGraph.search(x: longint): boolean;
var
work: link;
t1, t2, k: longint;
begin
search := false;
if dist[1, x] > len then exit;
search := true;
work := head[1, x];
while work <> nil do begin
k := work^.v;
if (not check[k]) and (dist[2, k] = dist[1, x] + 1) then begin
check[k] := true;
t1 := match[1, x];
t2 := match[2, k];
match[1, x] := k;
match[2, k] := x;
if (t2 = 0) or search(t2) then exit;
match[1, x] := t1;
match[2, k] := t2;
end;
work := work^.next;
end;
search := false;
end;
procedure TBipartiteGraph.init;
var
i: longint;
begin
for i:=1 to n do begin
head[1, i] := nil;
head[2, i] := nil;
tail[1, i] := nil;
tail[2, i] := nil;
end;
end;
procedure TBipartiteGraph.addEdge(x, y: longint);
var
work: link;
begin
new(work);
work^.next := nil;
work^.v := y;
if head[1, x] = nil then begin
head[1, x] := work;
tail[1, x] := work;
end
else begin
tail[1, x]^.next := work;
tail[1, x] := work;
end;
new(work);
work^.next := nil;
work^.v := x;
if head[2, y] = nil then begin
head[2, y] := work;
tail[2, y] := work;
end
else begin
tail[2, y]^.next := work;
tail[2, y] := work;
end;
end;
function TBipartiteGraph.maxMatch: longint; //hopcroft
var
qs, qe, i, k, s: longint;
work: link;
begin
fillchar(match, sizeof(match), 0);
repeat
fillchar(dist, sizeof(dist), 0);
qs := 1;
qe := 0;
for i:=1 to n do
if match[1, i] = 0 then begin
inc(qe);
q[qe] := i;
dist[1, i] := 1;
end;
len := maxlongint;
while qs <= qe do begin
work := head[1, q[qs]];
while work <> nil do begin
k := work^.v;
if dist[2, k] = 0 then begin
dist[2, k] := dist[1, q[qs]] + 1;
if match[2, k] <> 0 then begin
inc(qe);
q[qe] := match[2, k];
dist[1, match[2, k]] := dist[2, k] + 1;
end
else
if dist[2, k] < len then
len := dist[2, k]; //这里是最短增广路增广
end;
work := work^.next;
end;
inc(qs);
end;
if len = maxlongint then break;
fillchar(check, sizeof(check), false);
for i:=1 to n do
if match[1, i] = 0 then
search(i);
until false;
s := 0;
for i:=1 to n do
s := s + ord(match[1, i] <> 0);
maxMatch := s;
end;
begin
assign(input, fin);
assign(output, fout);
reset(input);
rewrite(output);
bip.init;
readln(n, m);
for i:=1 to m do begin
readln(x, y);
bip.addEdge(x, y);
end;
writeln(n-bip.maxMatch);
close(input);
close(output);
end.
阅读(237 次)