首页 > 代码库 > 【POJ3565】ANTS KM算法
【POJ3565】ANTS KM算法
【POJ3565】ANTS
题意：平面上有2*n个点，N白N黑。为每个白点找一个黑点与之连边，最后所有边不交叉。求一种方案。
题解：KM算法真是一个神奇的算法，虽然感觉KM能做的题用费用流都能做~
本题用到的结论：当选出的点对之间的距离之和最小时，一定使所有边都不交叉
这个感觉很容易理解，自己画画图就能看出来，就是难想啊
然后跑最小权值匹配，方法是将边权都变成相反数，然后跑最大权值匹配
不知道为什么以前写的KM算法会TLE，将求temp的过程拿到主函数里就过了
#include <cstdio>#include <cstring>#include <iostream>#include <cmath>using namespace std;int n;int xa[110],ya[110],xb[110],yb[110],va[110],vb[110],from[110],sta[110];double dis[110][110],la[110],lb[110],temp;int dfs(int x){ va[x]=1; for(int i=1;i<=n;i++) { if(!vb[i]&&fabs(la[x]+lb[i]-dis[x][i])<1e-6) { vb[i]=1; if(!from[i]||dfs(from[i])) { from[i]=x; return 1; } } } return 0;}int main(){ scanf("%d",&n); int i,j,k; for(i=1;i<=n;i++) scanf("%d%d",&xa[i],&ya[i]); for(i=1;i<=n;i++) scanf("%d%d",&xb[i],&yb[i]); for(i=1;i<=n;i++) for(j=1;j<=n;j++) dis[i][j]=-sqrt(1.0*(xa[i]-xb[j])*(xa[i]-xb[j])+(ya[i]-yb[j])*(ya[i]-yb[j])); for(i=1;i<=n;i++) for(j=2,la[i]=dis[i][1];j<=n;j++) la[i]=max(la[i],dis[i][j]); for(i=1;i<=n;i++) { while(1) { memset(va,0,sizeof(va)); memset(vb,0,sizeof(vb)); temp=99999999.999999; if(dfs(i)) break; for(j=1;j<=n;j++) if(va[j]) for(k=1;k<=n;k++) if(!vb[k]) temp=min(temp,la[j]+lb[k]-dis[j][k]); for(j=1;j<=n;j++) if(va[j]) la[j]-=temp; for(j=1;j<=n;j++) if(vb[j]) lb[j]+=temp; } } for(i=1;i<=n;i++) sta[from[i]]=i; for(i=1;i<=n;i++) printf("%d\n",sta[i]); return 0;}【POJ3565】ANTS KM算法
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。