本文主要是介绍hdu 4463 Outlets(最小生成树，kruskal，前向星)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目：http://acm.hdu.edu.cn/showproblem.php?pid=4463
最小生成树的应用，但是要先把其中两个点连接起来，然后选取剩余的n-2条边。为了和纯粹的kruskal算法尽量相似，我在结构体上多下了功夫，可能看起来有点复杂。
#include <iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<map>
using namespace std;
int n,p,q,cnt;
double ans;
struct point{int x,y,dex;point operator =(point other){x=other.x;y=other.y;dex=other.dex;return *this;}bool operator !=(point other){return (x!=other.x||y!=other.y);}bool operator==(point other){return (x==other.x&&y==other.y);}
}pt[60];
struct Cmp {bool operator()( const point p1, const point p2 ) const {return p1.dex<p2.dex;}
};
map<point,point,Cmp> mp;
point find(point a){if(mp[a]==a)return a;return find(mp[a]);
}
double dis(point a,point b){return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
struct Edge{point from,to;double w;bool operator<(const Edge &b)const {return w<b.w;}
}edge[2500];
void swap(int &a,int &b){int t=a;a=b;b=t;
}
void showpoint(point a){cout<<a.dex<<" "<<a.x<<" "<<a.y<<endl;
}
void kruskal(){int top=1;sort(edge,edge+cnt);for(int i=0;i<cnt;i++){if(top==n-1)break;point q1=find(edge[i].from),q2=find(edge[i].to);//showpoint(q1); showpoint(q2);if(q1!=q2){mp[q1]=q2;ans+=edge[i].w;//cout<<ans<<endl;top++;}}
}
void showmp(){for(map<point,point,Cmp>::iterator ix=mp.begin();ix!=mp.end();ix++){showpoint(ix->first);showpoint(ix->second);}
}
int main()
{//freopen("cin.txt","r",stdin);while(cin>>n&&n){ans=0;cin>>p>>q;if(p>q)swap(p,q);for(int i=1;i<=n;i++){int a,b;scanf("%d%d",&a,&b);pt[i].x=a;pt[i].y=b;pt[i].dex=i;mp[pt[i]]=pt[i];}//showmp();cnt=0;for(int i=1;i<n;i++){for(int j=i+1;j<=n;j++){edge[cnt].from=pt[i];edge[cnt].to=pt[j];edge[cnt++].w=dis(pt[i],pt[j]);}}ans+=dis(pt[p],pt[q]);mp[pt[p]]=pt[q];kruskal();printf("%.2lf\n",ans);}return 0;
}这篇关于hdu 4463 Outlets(最小生成树，kruskal，前向星)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
