题意:给你n个点(坐标表示),求删除其中一个点的最小生成树中长度最小的那个。
思路:由于n的范围是0~50,因此直接枚举每个点,然后求最小生成树,最后取最小值即可。
写的时候由于prime没写好,贡献了4个wrong……orz,真是伤心,看来我的基本功还是练得不够好啊。
代码:
#include <iostream> #include<cstdio> #include<cstring> #include<string> #include<algorithm> #include<map> #include<queue> #include<cmath> #include<vector> #define inf 0x3f3f3f3f #define Inf 0x3FFFFFFFFFFFFFFFLL #define eps 1e-8 #define pi acos(-1.0) using namespace std; int n; double m[55][55]; double len[55]; bool vis[55],flag[55]; double minlen; const double maxd=999999999; struct Points { int x,y; }; Points p[55]; double getLen(int a,int b) { double u=(p[a].x-p[b].x)*(p[a].x-p[b].x); double v=(p[a].y-p[b].y)*(p[a].y-p[b].y); return sqrt(u+v); } void prim() { memset(vis,0,sizeof(vis)); int z=flag[0]?1:0; for(int i=0;i<n;++i) { if(!flag[i]) { len[i]=m[z][i]; } } vis[z]=true; double minnum; int dir; double sum=0; for(int i=1;i<n-1;++i) { minnum=maxd; for(int j=0;j<n;++j) { if(!vis[j]&&!flag[j]&&len[j]<minnum) { minnum=len[j]; dir=j; } } sum+=minnum; vis[dir]=true; for(int k=0;k<n;++k) { if(!flag[k]) { len[k]=min(len[k],m[dir][k]); } } } minlen=min(minlen,sum); } int main() { //freopen("in.txt","r",stdin); //freopen("out.txt","w",stdout); int t; cin>>t; while(t--) { cin>>n; for(int i=0;i<n;++i) { cin>>p[i].x>>p[i].y; } for(int i=0;i<n;++i) { for(int j=0;j<n;++j) { m[i][j]=m[j][i]=getLen(i,j); } } memset(flag,0,sizeof(flag)); minlen=maxd; flag[0]=true; prim(); for(int i=1;i<n;++i) { flag[i-1]=false; flag[i]=true; prim(); } printf("%.2lf\n",minlen); } return 0; }