这道题真的不难，但是细节挺多（具体见程序）

题目本身而言，显然是个费用流模型（或者写KM）

1 type node=record  2        point,next,flow,cost:longint;  3      end;  4   5 var p,x,y,pre,cur,d:array[0..80] of longint;  6     v:array[0..80] of boolean;  7     q:array[0..500010] of longint;  8     edge:array[0..200010] of node;  9     a:array[0..80,0..80] of longint; 10     na:array[0..80] of string[21]; 11     t,n,i,len,j,k:longint; 12     ef:boolean; 13     s:string; 14     ch:char; 15  16 function find(x:string):longint; 17   var i:longint; 18   begin 19     for i:=1 to 2*n do 20       if na[i]=x then exit(i); 21   end; 22  23 function check(l,r:longint):boolean; 24   var i:longint; 25   begin 26     for i:=1 to 2*n do 27       if (i<>l) and (i<>r) then 28         if ((x[i]<=x[l]) and (x[i]>=x[r])) or ((x[i]>=x[l]) and (x[i]<=x[r])) then 29           if ((y[i]<=y[l]) and (y[i]>=y[r])) or ((y[i]>=y[l]) and (y[i]<=y[r])) then 30             if (x[i]-x[l])*(y[i]-y[r])=(x[i]-x[r])*(y[i]-y[l]) then 31             begin  //注意是线段上的点 32               exit(false); 33             end; 34     exit(true); 35   end; 36  37 procedure add(x,y,f,w:longint); 38   begin 39     inc(len); 40     edge[len].point:=y; 41     edge[len].flow:=f; 42     edge[len].cost:=w; 43     edge[len].next:=p[x]; 44     p[x]:=len; 45   end; 46  47 function spfa:boolean; 48   var i,j,f,r,x,y:longint; 49   begin 50     for i:=1 to t do 51       d[i]:=-100000007; 52     d[0]:=0; 53     f:=1; 54     r:=1; 55     fillchar(v,sizeof(v),false); 56     q[1]:=0; 57     v[0]:=true; 58     while f<=r do 59     begin 60       x:=q[f]; 61       v[x]:=false; 62       i:=p[x]; 63       while i<>-1 do 64       begin 65         y:=edge[i].point; 66         if edge[i].flow>0 then 67           if d[x]+edge[i].cost>d[y] then 68           begin 69             pre[y]:=x; 70             cur[y]:=i; 71             d[y]:=d[x]+edge[i].cost; 72             if not v[y] then 73             begin 74               inc(r); 75               q[r]:=y; 76               v[y]:=true; 77             end; 78           end; 79         i:=edge[i].next; 80       end; 81       inc(f); 82     end; 83     if d[t]=-100000007 then exit(false) else exit(true); 84   end; 85  86 function maxcost:longint; 87   var i,j:longint; 88   begin 89     maxcost:=0; 90     while spfa do 91     begin 92       maxcost:=maxcost+d[t]; 93       i:=t; 94       while i<>0 do 95       begin 96         j:=cur[i]; 97         dec(edge[j].flow); 98         inc(edge[j xor 1].flow); 99         i:=pre[i];100       end;101     end;102   end;103 104 begin105   len:=-1;106   fillchar(p,sizeof(p),255);107   readln(k);108   readln(n);109   for i:=1 to 2*n do110   begin111     readln(x[i],y[i],ch,na[i]);112     for j:=1 to length(na[i]) do113       na[i][j]:=upcase(na[i][j]);  //注意不区分大小写114   end;115   t:=2*n+1;116   for i:=1 to n do117   begin118     add(0,i,1,0);119     add(i,0,0,0);120     add(i+n,t,1,0);121     add(t,i+n,0,0);122   end;123 124   for i:=1 to n do125     for j:=n+1 to 2*n do126       a[i,j]:=1;   //注意127   ef:=true;128   while ef do129   begin130     s:='';131     read(ch);132     while ch<>' ' do133     begin134       s:=s+upcase(ch);135       if s='END' then ef:=false;  //大坑，有的人名字里会带end136       read(ch);137       if not ef and (ord(ch)>=65)  then138         ef:=true139       else if not ef then break;140     end;141     if not ef then break;142     i:=find(s);143     s:='';144     read(ch);145     while ch<>' ' do146     begin147       s:=s+upcase(ch);148       read(ch);149     end;150     j:=find(s);151     readln(a[i,j]);152     a[j,i]:=a[i,j];153   end;154   for i:=1 to n do155     for j:=n+1 to 2*n do156       if (sqr(x[i]-x[j])+sqr(y[i]-y[j])<=sqr(k)) and check(i,j) then157       begin158         add(i,j,1,a[i,j]);159         add(j,i,0,-a[i,j]);160       end;161   writeln(maxcost);162 end.