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.
|