BZOJ 2539

传送门

黑书上二分图最优匹配的例题尼玛黑书上说了跟没说一样

直接上KM或费用流就可以了 但是好坑啊 QAQ

是否共线直接暴力用叉积和横纵坐标比较就行,名字用哈希乱搞,但是坑真多 = =

  1. 名字大小写不分 Shit=SHIT

  2. 题目未涉及的两人之间缘分为1

  3. 如果发现题目给出的两人的线无法连接,则记得把权值赋为-inf

  4. 还有个我爬了半天的坑是:尼玛没涉及的俩人如果超射程的话连1的缘分也没有,不要这么绝情好不好…

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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
program bzoj_2539;
const mo=1007;
inf=maxlongint>>1;
type rec=record x,y,h:longint; end;
var pos:array[0..mo]of longint;
per:array[1..60]of rec;
w:array[1..30,1..30]of longint;
lx,ly,slack,p:array[1..30]of longint;
vx,vy:array[1..30]of boolean;
k,n,i,endf,a,b,t,ans:longint;
s:string;
c:char;
function hash:longint;
var i:longint;
begin
hash:=0;
for i:=1 to length(s) do hash:=(hash*107+ord(s[i])*31)mod mo;
end;
function dis(x1,y1,x2,y2:longint):longint;
begin
exit(sqr(x2-x1)+sqr(y2-y1));
end;
function bulb(a,b:longint):boolean;
var i:longint;
begin
for i:=1 to n<<1 do
begin
if (i=a)or(i=b) then continue;
if (per[i].x-per[a].x)*(per[i].x-per[b].x)>0 then continue;
if (per[i].y-per[a].y)*(per[i].y-per[b].y)>0 then continue;
if (per[i].x-per[a].x)*(per[b].y-per[i].y)=(per[b].x-per[i].x)*(per[i].y-per[a].y) then exit(true);
end;
exit(false);
end;
function path(x:longint):boolean;
var i,t:longint;
begin
vx[x]:=true;
for i:=1 to n do
begin
if vy[i] then continue;
t:=lx[x]+ly[i]-w[x,i];
if t=0 then
begin
vy[i]:=true;
if (p[i]=0)or(path(p[i])) then
begin
p[i]:=x;
exit(true);
end;
end else if t<slack[i] then slack[i]:=t;
end;
exit(false);
end;
procedure KM;
var i,x,d:longint;
begin
fillchar(ly,sizeof(ly),0);
fillchar(p,sizeof(p),0);
for x:=1 to n do
begin
fillchar(slack,sizeof(slack),$3f);
repeat
fillchar(vx,sizeof(vx),false);
fillchar(vy,sizeof(vy),false);
if path(x) then break;
d:=inf;
for i:=1 to n do if (not vy[i])and(slack[i]<d) then d:=slack[i];
for i:=1 to n do if vx[i] then dec(lx[i],d);
for i:=1 to n do if vy[i] then inc(ly[i],d);
until false;
end;
for i:=1 to n do if p[i]<>0 then inc(ans,w[p[i],i]);
end;
begin
readln(k);
readln(n);
for i:=1 to n<<1 do
begin
read(per[i].x,per[i].y,c);
read(c);
s:='';
while c in ['A'..'z'] do
begin
s:=s+c;
read(c);
end;
s:=upcase(s);
readln;
pos[hash]:=i;
end;
for a:=1 to n do
for b:=n+1 to n<<1 do
if (dis(per[a].x,per[a].y,per[b].x,per[b].y)<=k*k)and(not bulb(a,b)) then w[a,b-n]:=1 else w[a,b-n]:=-inf;
s:='END';
endf:=hash;
fillchar(lx,sizeof(lx),0);
repeat
read(c);
s:='';
while c in ['A'..'z'] do
begin
s:=s+c;
read(c);
end;
s:=upcase(s);
a:=hash;
if a=endf then break;
read(c);
s:='';
while c in ['A'..'z'] do
begin
s:=s+c;
read(c);
end;
s:=upcase(s);
b:=hash;
if pos[a]>n then
begin
t:=a;
a:=b;
b:=t;
end;
a:=pos[a];
b:=pos[b];
readln(t);
if (dis(per[a].x,per[a].y,per[b].x,per[b].y)>k*k)or(bulb(a,b)) then continue;
w[a,b-n]:=t;
if w[a,b-n]>lx[a] then lx[a]:=w[a,b-n];
until false;
ans:=0;
KM;
writeln(ans);
end.