自动搬运

查看原文

来自洛谷，原作者为

	Khassar **

搬运于2025-08-24 21:25:46，当前版本为作者最后更新于2018-01-04 10:57:33，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

楼下说的很对啊，这题就是一个带权二分图最大匹配，只不过怎么没人用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;
}