BZOJ 1854

1191的升级版,没写的戳我

传送门

每种装备的两个属性向这个装备的序号连边,因为边数点数好大所以要用链表

这道题直接用裸Hungary会在BZOJ上TLE 尼玛本地刚过2s啊交上去就T 6s+

瞅了瞅代码,发现每次增广都要fillchar一个10^6大小的布尔数组有点吃不消啊…

考虑一下优化的办法,因为每个代表装备的点只有两个点向其连边,所以直接记录下是与两个点中的哪一个连接,判断条件改一下就好了,这样也省了fillchar

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
program bzoj_1854;
const maxn=1000000;
var l:array[1..2*maxn]of record ed,pre:longint; end;
p,num:array[1..maxn]of longint;
lst:array[1..10000]of longint;
n,i,a,b,tot,cnt:longint;
procedure link(a,b:longint);
begin
inc(tot);
l[tot].pre:=lst[a];
lst[a]:=tot;
l[tot].ed:=b;
end;
function path(x:longint):boolean;
var k:longint;
begin
k:=lst[x];
while k<>0 do
begin
if num[l[k].ed]<>cnt then
begin
num[l[k].ed]:=cnt;
if (p[l[k].ed]=0)or(path(p[l[k].ed])) then
begin
p[l[k].ed]:=x;
exit(true);
end;
end;
k:=l[k].pre;
end;
exit(false);
end;
function hungary:longint;
var i:longint;
begin
cnt:=0;
for i:=1 to 10001 do
begin
inc(cnt);
if not path(i) then break;
end;
exit(i-1);
end;
begin
readln(n);
tot:=0;
for i:=1 to n do
begin
readln(a,b);
link(a,i);
link(b,i);
end;
writeln(hungary);
end.