这道题真的不难，但是细节挺多（具体见程序）
题目本身而言，显然是个费用流模型（或者写KM）
type node=record
point,next,flow,cost:longint;
end; var p,x,y,pre,cur,d:array[..] of longint;
v:array[..] of boolean;
q:array[..] of longint;
edge:array[..] of node;
a:array[..,..] of longint;
na:array[..] of string[];
t,n,i,len,j,k:longint;
ef:boolean;
s:string;
ch:char; function find(x:string):longint;
var i:longint;
begin
for i:= to *n do
if na[i]=x then exit(i);
end; function check(l,r:longint):boolean;
var i:longint;
begin
for i:= to *n do
if (i<>l) and (i<>r) then
if ((x[i]<=x[l]) and (x[i]>=x[r])) or ((x[i]>=x[l]) and (x[i]<=x[r])) then
if ((y[i]<=y[l]) and (y[i]>=y[r])) or ((y[i]>=y[l]) and (y[i]<=y[r])) then
if (x[i]-x[l])*(y[i]-y[r])=(x[i]-x[r])*(y[i]-y[l]) then
begin //注意是线段上的点
exit(false);
end;
exit(true);
end; procedure add(x,y,f,w:longint);
begin
inc(len);
edge[len].point:=y;
edge[len].flow:=f;
edge[len].cost:=w;
edge[len].next:=p[x];
p[x]:=len;
end; function spfa:boolean;
var i,j,f,r,x,y:longint;
begin
for i:= to t do
d[i]:=-;
d[]:=;
f:=;
r:=;
fillchar(v,sizeof(v),false);
q[]:=;
v[]:=true;
while f<=r do
begin
x:=q[f];
v[x]:=false;
i:=p[x];
while i<>- do
begin
y:=edge[i].point;
if edge[i].flow> then
if d[x]+edge[i].cost>d[y] then
begin
pre[y]:=x;
cur[y]:=i;
d[y]:=d[x]+edge[i].cost;
if not v[y] then
begin
inc(r);
q[r]:=y;
v[y]:=true;
end;
end;
i:=edge[i].next;
end;
inc(f);
end;
if d[t]=- then exit(false) else exit(true);
end; function maxcost:longint;
var i,j:longint;
begin
maxcost:=;
while spfa do
begin
maxcost:=maxcost+d[t];
i:=t;
while i<> do
begin
j:=cur[i];
dec(edge[j].flow);
inc(edge[j xor ].flow);
i:=pre[i];
end;
end;
end; begin
len:=-;
fillchar(p,sizeof(p),);
readln(k);
readln(n);
for i:= to *n do
begin
readln(x[i],y[i],ch,na[i]);
for j:= to length(na[i]) do
na[i][j]:=upcase(na[i][j]); //注意不区分大小写
end;
t:=*n+;
for i:= to n do
begin
add(,i,,);
add(i,,,);
add(i+n,t,,);
add(t,i+n,,);
end; for i:= to n do
for j:=n+ to *n do
a[i,j]:=; //注意
ef:=true;
while ef do
begin
s:='';
read(ch);
while ch<>' ' do
begin
s:=s+upcase(ch);
if s='END' then ef:=false; //大坑，有的人名字里会带end
read(ch);
if not ef and (ord(ch)>=) then
ef:=true
else if not ef then break;
end;
if not ef then break;
i:=find(s);
s:='';
read(ch);
while ch<>' ' do
begin
s:=s+upcase(ch);
read(ch);
end;
j:=find(s);
readln(a[i,j]);
a[j,i]:=a[i,j];
end;
for i:= to n do
for j:=n+ to *n do
if (sqr(x[i]-x[j])+sqr(y[i]-y[j])<=sqr(k)) and check(i,j) then
begin
add(i,j,,a[i,j]);
add(j,i,,-a[i,j]);
end;
writeln(maxcost);
end.