2012 Asia Hangzhou Regional Contest--hdu4463Outlets(mst)
题目请戳这里
题目大意：二维平面内给n个点，求将所有点连通需要的最小代价，代价为点间距，其中给定2个点必须直接相连。
题目分析：
2012杭州现场赛四大水题之三。
裸的最小生成树。prime求最小生成树。给定的2个点先加到初始集合中，再扩展n-2个点即可。
详情请见代码：
#include <iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<cmath>#include<cstdlib>#include<cctype>#include<map>#include<vector>#include<set>#include<queue>#include<string>using namespace std;const int N = 55;const int M = 10000005;const int INF = 0x3f3f3f3f;double dis[N][N];int n;struct node{ double x,y;}pt[N];double ans;double dist[N];bool flag[N];double getdis(int x,int y){ return sqrt((pt[x].x - pt[y].x) * (pt[x].x - pt[y].x) + (pt[x].y - pt[y].y) * (pt[x].y - pt[y].y));}void prime(int a,int b){ int i,j; ans += dis[a][b]; memset(flag,false,sizeof(flag)); for(i = 1;i <= n;i ++) dist[i] = 10000000.0; for(i = 1;i <= n;i ++) dist[i] = min(dis[a][i],dis[b][i]); dist[a] = dist[b] = 0; flag[a] = flag[b] = true; for(i = 1;i < n - 1;i ++) { double mx = 10000000.0; int u = -1; for(j = 1;j <= n;j ++) { if(flag[j] == false && dist[j] < mx) { mx = dist[j]; u = j; } } ans += mx; flag[u] = true; for(j = 1;j <= n;j ++) { if(flag[j] == false) dist[j] = min(dist[j],dis[u][j]); } }}int main(){ int i,j,a,b; while(scanf("%d",&n),n) { scanf("%d%d",&a,&b); for(i = 1;i <= n;i ++) scanf("%lf%lf",&pt[i].x,&pt[i].y); for(i = 1;i <= n;i ++) { dis[i][i] = 0; for(j = 1;j < i;j ++) dis[i][j] = dis[j][i] = getdis(i,j); } ans = 0; prime(a,b); printf("%.2f\n",ans); } return 0;}