题意：2n个人，给出2n个人的坐标和姓名，然后给出一些人之间的好感，没有给出的默认好感为1。两个人之间可以匹配的条件是：两个人之间的欧几里得距离不超过给定的距离m且两人所连的线段不经过其他人。求能匹配上的人的缘分总和最大
建图慢慢建就好，然后KM匹配裸题
坑点：（1）据说坐标并没有保证是整数，
（2）给出的两人之间的好感可能为0，所以不能匹配的人之间的边要建成负无穷
type rec=record xx,yy:double; nm:string; end; var n,m,ll,num,p1,p2:longint; s,s1,s2 :string; ch :char; i,j,k :longint; visx,visy :array[0.. 35] of boolean; link,lx,ly :array[0..35] of longint; w :array[0..35,0..35] of longint; a :array[0..60] of rec; function min(a,b:double):double; begin if a<b then exit(a) else exit(b); end; function max(a,b:double):double; begin if a<b then exit(b) else exit(a); end; function find(x:longint):boolean; var i:longint; begin visx[x]:=true; for i:=1 to n do if not visy[i] and (lx[x]+ly[i]=w[x,i]) then begin visy[i]:=true; if (link[i]=0) or (find(link[i])) then begin link[i]:=x; exit(true); end; end; exit(false); end; procedure km; var i,j,k:longint; ans,tt:longint; begin ans:=0; for i:=1 to n do begin ly[i]:=0; lx[i]:=-maxlongint; for j:=1 to n do if w[i,j]>lx[i] then lx[i]:=w[i,j]; end; // for i:=1 to n do begin while true do begin fillchar(visx,sizeof(visx),false); fillchar(visy,sizeof(visy),false); if find(i) then break; // tt:=maxlongint; for j:=1 to n do if visx[j] then for k:=1 to n do if (w[j,k]<>-maxlongint) then if not visy[k] and (lx[j]+ly[k]-w[j,k]<tt) then tt:=lx[j]+ly[k]-w[j,k]; // for j:=1 to n do begin if visx[j] then dec(lx[j],tt); if visy[j] then inc(ly[j],tt); end; end; end; // for i:=1 to n do if link[i]>0 then inc(ans,w[link[i],i]); writeln(ans); end; begin readln(m); readln(n); for i:=1 to n*2 do begin read(a[i].xx,a[i].yy); read(ch); readln(a[i].nm); ll:=length(a[i].nm); for j:=1 to ll do a[i].nm[j]:=upcase(a[i].nm[j]); end; // for i:=1 to n do for j:=1 to n do w[i,j]:=1; // readln(s); while (s<>'End') do begin ll:=length(s); for j:=1 to ll do s[j]:=upcase(s[j]); s1:=copy(s,1,pos(' ',s)-1); delete(s,1,pos(' ',s)); s2:=copy(s,1,pos(' ',s)-1); delete(s,1,pos(' ',s)); val(s,num); // for j:=1 to n*2 do if a[j].nm=s1 then break; p1:=j; for j:=1 to n*2 do if a[j].nm=s2 then break; p2:=j; // if p1>n then w[p2,p1-n]:=num else w[p1,p2-n]:=num; readln(s); end; // for i:=1 to n do for j:=n+1 to 2*n do if sqr(a[i].xx-a[j].xx)+sqr(a[i].yy-a[j].yy)>sqr(m) then w[i,j-n]:=-maxlongint else begin for k:=1 to 2*n do if (k<>i) and (k<>j) then if (a[k].yy-a[i].yy)*(a[j].xx-a[i].xx)=(a[j].yy-a[i].yy)*(a[k].xx-a[i].xx) then if (a[k].xx<=max(a[i].xx,a[j].xx)) and (a[k].xx>=min(a[i].xx,a[j].xx)) then if (a[k].yy>=min(a[i].yy,a[j].yy)) and (a[k].yy<=max(a[i].yy,a[j].yy)) then begin w[i,j-n]:=-maxlongint; break; end; end; KM; end. ——by Eirlys
