题目链接
题目大意
有n个白点和n个黑点 每个白点要与黑点链接 要求所有线段都不相交
题目思路
若是两个线段相交 就可以让两个交点交换一下
如下图
变为下图
这样不会交叉并且由于三角线两边大于第三边可知 长度一定变小
因此原题让所有线段都不相交可以转化为让所有线段的和最小
接下来将题目转化为 二分图最大全匹配的模板 白点黑点分别作为左右图
每个点之间的距离 作为边权
接下来直接套KM板子就好
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;
const int inf=0x3f3f3f3f;
const ll inf_ll = 1000000.0;
const int maxn=1e5+10;
const int N=200+10;
int n;
struct node{double x,y;
}e[N*N];
double w[N][N];
ll mb[N+7],vb[N+7],p[N+7];
double ka[N+7],kb[N+7],c[N+7];//ll qf,qb,q[N+7];
void Bfs(int u){//模板ll a,v=0,vl=0;double d;for(int i=1;i<=n;i++) p[i]=0,c[i]=1000000.0;mb[v]=u;do {a=mb[v],d=inf_ll,vb[v]=1;for(int b=1;b<=n;b++)if(!vb[b]){if(c[b]>ka[a]+kb[b]-w[a][b])c[b]=ka[a]+kb[b]-w[a][b],p[b]=v;if(c[b]<d) d=c[b],vl=b;}for(int b=0;b<=n;b++)if(vb[b]) ka[mb[b]]-=d,kb[b]+=d;else c[b]-=d;v=vl;} while(mb[v]);while(v) mb[v]=mb[p[v]],v=p[v];
}
ll KM(){for(int i=1;i<=n;i++) mb[i]=0,ka[i]=kb[i]=0.0;for(int a=1;a<=n;a++){for(int b=1;b<=n;b++) vb[b]=0;Bfs(a);}ll res=0;for(int b=1;b<=n;b++) res+=w[mb[b]][b];return res;
}
double dis(const node &x,const node &y){return sqrt((x.x-y.x)*(x.x-y.x)+(x.y-y.y)*(x.y-y.y));
}
int main()
{cin>>n;int a,b;for(int i=1;i<=n;i++){cin>>e[i].x>>e[i].y;}for(int i=1;i<=n;i++){cin>>e[i+n].x>>e[i+n].y;//白 }for(int i=1;i<=n;i++)//白 {for(int j=1;j<=n;j++){//add(i,j,dis(e[i+n],e[j]));w[i][j]=dis(e[i+n],e[j]);w[i][j]*=-1.0;//求最小值别忘乘-1}}KM();for(int i=1;i<=n;i++)cout<<mb[i]<<endl;return 0;
}还有一道带权匹配KM题
2021牛客第五场J-Jewels
原题链接
题解博客