题解 P1500 【丘比特的烦恼】
楼下说的很对啊，这题就是一个带权二分图最大匹配，只不过怎么没人用KM写呢？所以我就在此献丑，奉上一篇KM的题解。
我们把男子放到左边，女子放到右边，为这两个之间建一条边权为缘分的边，然后跑KM就可以了。
坑点嘛。。。
①字符串大小写不敏感->挂40分
②没说的人之间缘分为1->挂40分
③不能连的人之间之间缘分要设为负无穷->挂10分
尤其是这个③，跟我同机房的dalao写的费用流直接无视第三点，我问的时候他还一脸mengbi，可能是费用流自己就能判过去吧，反正KM不行。并且它给的特别缘分有很多是负的。至于这些为什么是挂怎么多分，emmmmm~~~
并且这道题既然能用KM做，就说明它有一个隐式的条件——有完备匹配，这点在题目中并没有说
下面简单介绍一下KM的算法思想，当然是我从我的另一篇题解复制的，不想看的可以跳过去直接看代码注释了
首先，介绍一个重要的定理：
我们定义顶标：
lx[i],ly[j],i∈左边，j∈右边，并且对于任意w[i][j],都有lx[i]+ly[j]>=w[i][j]；
我们再从原图中抽出lx[i]+ly[j]=w[i][j]的边建立一个相等子图，如果相等子图有完美匹配（就是无边权，全匹配的那个），那么这个完美匹配就是原图的最佳完美匹配。
这个定理的证明也十分简单，这里我就不证明了，有兴趣的可以自行百度。
有了这个定理我们就可以用KM(匈牙利算法)求解此题了。
具体的方法就是，不断的修改顶标让它有一个合适的值，使得相等子图有完美匹配。实现起来就是先开心地设一个顶标初值（一般是ly=0,lx=max(w[i][j])），然后开始KM，如果找到了一条增广路，就找到了吧；如果没有，那它一定是尝试访问了一些左边的点（比如q个）我们把它们加入S,然后访问了q-1个右边的点,我们把它们加入T（S,T是两个集合）。
然后把lx[i],i∈S都减去一个松弛量a，ly[j],j∈T，都加上一个a，这样就会有一些不在T中的点和在S中的点之间的边能够进入相等子图，同时已经在相等子图里的边不出去，继续进行KM直到匹配了这个点为止。
至于找a的方法，为了保证进来的边是能进来的之中最大的，同时又有边进来，
a=min{lx[i]+ly[j]-w[i][j]|i∈S，j∉T}，这个过程就n^2暴力枚举就好了，因此整个算法时间复杂度为n^4，当然还有一个n^3的优化方法，不过n^4就能0ms秒杀此题，所以这里就不用了。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<cstdlib>
#include<string>
#include<queue>
#include<map>
#include<vector>
#include<ctime>
#define ll long long
#define R register
#define IL inline
#define Rf(a,b,c) for(R int (a)=(b);(a)<=(c);++(a))
#define Tf(a,b,c) for(R int (a)=(b);(a)>=(c);--(a))
#define MP make_pair
#define PA pair<int,int>
#define MES(a,b) memset((a),(b),sizeof((a)))
#define MEC(a,b) memcpy((a),(b),sizeof((b)))
#define D double
using namespace std;
const int N=50;
const D eps=1e-9;
int n,lx[N],ly[N],link[N],w[N][N],ans;
bool S[N],T[N];
D k;
string s1,s2;
map <string,int> idm,idw;//人的编号就开map搞一搞就行了
struct node {
int x,y;
}man[N],wom[N];
IL int read() {
int x=0,f=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x*=10;x+=(ch-'0');ch=getchar();}
return x*f;
}
IL void write(int x) {
if(x<0) putchar('-'),x=-x;
if(x>9) write(x/10);
putchar(x%10+'0');
}
bool dfs(int x) {//这就是一般的二分图匹配
S[x]=true;//把左边的点都加入S
Rf(i,1,n) if(lx[x]+ly[i]==w[x][i]&&!T[i]) {
//判断这条边是否在相等子图里，不要再建图了
T[i]=true;//右边的点加入T
if(!link[i]||dfs(link[i])) {
link[i]=x;
return true;
}
}
return false;
}
IL void update() {//n^2暴力找a，并修改
R int a=1<<30;
Rf(i,1,n) if(S[i])
Rf(j,1,n) if(!T[j])
a=min(a,lx[i]+ly[j]-w[i][j]);
Rf(i,1,n) {
if(S[i]) lx[i]-=a;
if(T[i]) ly[i]+=a;
}
}
IL void KM() {
Rf(i,1,n) {
link[i]=lx[i]=ly[i]=0;
lx[i]=-1e9;//这句话好像可以不要
Rf(j,1,n) lx[i]=max(lx[i],w[i][j]);
}
Rf(i,1,n) while(true) {
Rf(j,1,n) S[j]=T[j]=false;
if(dfs(i)) break;
else update();
}
}
void Turn(string &s){//把字符串都转化成大写的
for(string::iterator it=s.begin();it!=s.end();it++)
if(*it>='a') *it=*it-'a'+'A';
}
IL D cal(int i,int j) {//算两点之间的距离
return sqrt(1.0*(man[i].x-wom[j].x)*(man[i].x-wom[j].x)+1.0*(man[i].y-wom[j].y)*(man[i].y-wom[j].y));
}
signed main()
{
k=read();n=read();
Rf(i,1,n) {//定坐标
R int u=read(),v=read();
cin>>s1;
Turn(s1);
idm[s1]=i;
man[i].x=u;man[i].y=v;
}
Rf(i,1,n) {
R int u=read(),v=read();
cin>>s1;
Turn(s1);
idw[s1]=i;
wom[i].x=u;wom[i].y=v;
}
Rf(i,1,n) Rf(j,1,n) w[i][j]=1;//普遍缘分的
cin>>s1;
while(s1!="End") {//特别缘分的
cin>>s2;R int val=read();
Turn(s1);Turn(s2);
if(!idm[s1]) swap(s1,s2);//保证男在前
R int I=idm[s1],J=idw[s2];
w[I][J]=val;
cin>>s1;
}
Rf(I,1,n) Rf(J,1,n) {//暴力枚举两点是否可连
R D l;
if((l=cal(I,J))<=k) {//距离是否太远
R int pd=1;
//枚举中间插足的，无论男女
//看三点中是否有两短距离等于一长距离
Rf(i,1,n) {
if(i==I) continue;
D l1=sqrt(1.0*(man[i].x-wom[J].x)*(man[i].x-wom[J].x)+
1.0*(man[i].y-wom[J].y)*(man[i].y-wom[J].y));
D l2=sqrt(1.0*(man[i].x-man[I].x)*(man[i].x-man[I].x)+
1.0*(man[i].y-man[I].y)*(man[i].y-man[I].y));
if(fabs(l-l1-l2)<eps) {
pd=0;break;
}
}
if(pd) Rf(j,1,n) {
if(j==J) continue;
R D l1=sqrt(1.0*(wom[J].x-wom[j].x)*(wom[J].x-wom[j].x)+
1.0*(wom[J].y-wom[j].y)*(wom[J].y-wom[j].y));
R D l2=sqrt(1.0*(man[I].x-wom[j].x)*(man[I].x-wom[j].x)+
1.0*(man[I].y-wom[j].y)*(man[I].y-wom[j].y));
if(fabs(l-l1-l2)<eps) {
pd=0;break;
}
}
if(!pd) w[I][J]=-1e9;
}else w[I][J]=-1e9;
}
KM();
Rf(i,1,n) ans+=lx[i]+ly[i];//顶标和即是答案
write(ans);
return 0;
}