首页 > 代码库 > UVALive 4043 转化最佳完美匹配
UVALive 4043 转化最佳完美匹配
首先黑点和白点是组成一个二分图这毫无疑问
关键是题目中要求的所有黑白配的线不能交叉。。。一开始我也没想到这个怎么转化为二分图里面的算法。
后来看书才知道,如果两两交叉,则可以把两根线当四边形的对角线,连四边形的两条边,则肯定不交叉,而且一个很明显的特征是,不交叉的两条线的他们的长度和 一定比交叉线的长度和小。
于是我们只要求出最小长度的线,就必定是不相交的。那就要用到最佳完美匹配了,首先算出两两点的欧几里得距离,然后取负数,这样走一遍匹配,得到的必定是最短的欧几里得距离,即不相交的线
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> using namespace std; struct node { int x,y; } n1[110],n2[110]; int n,S[110],T[110],lefts[110],rights[110]; double w[110][110],lx[110],ly[110]; bool eq(double a, double b) { return fabs(a-b) < 1e-9; } bool dfs(int u) { S[u]=1; for (int v=1;v<=n;v++)if(eq(lx[u]+ly[v],w[u][v]) && !T[v]){ T[v]=1; if (!lefts[v]|| dfs(lefts[v])){ lefts[v]=u; rights[u]=v; return true; } } return false; } void up() { double a=1e30; for (int i=1;i<=n;i++) if (S[i]) for (int j=1;j<=n;j++) if (!T[j]) { a=min(a,lx[i]+ly[j]-w[i][j]); } for (int i=1;i<=n;i++){ if (S[i]) lx[i]-=a; if (T[i]) ly[i]+=a; } } void KM() { int i,j; for (i=1;i<=n;i++){ lefts[i]=lx[i]=ly[i]=0; for (j=1;j<=n;j++){ lx[i]=max(lx[i],w[i][j]); } } for (i=1;i<=n;i++){ for (;;){ memset(S,0,sizeof S); memset(T,0,sizeof T); if (dfs(i)) break; else up(); } } } int main() { while (scanf("%d",&n)!=EOF) { for (int i=1;i<=n;i++) scanf("%d%d",&n1[i].x,&n1[i].y); for (int i=1;i<=n;i++) scanf("%d%d",&n2[i].x,&n2[i].y); for (int i=1;i<=n;i++) for (int j=1;j<=n;j++){ w[i][j]=(double)(n1[i].x-n2[j].x)*(n1[i].x-n2[j].x)+(double)(n1[i].y-n2[j].y)*(n1[i].y-n2[j].y); w[i][j]=-sqrt(w[i][j]); } KM(); for (int i=1;i<=n;i++) printf("%d\n",rights[i]); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。