BZOJ

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.