首页 > 代码库 > HDU 1875 畅通工程再续
HDU 1875 畅通工程再续
最小生成树
ps:这个间接排序函数看起来挺高大上的~~
1 #include <iostream> 2 #include <cstring> 3 #include <cstdio> 4 #include <algorithm> 5 #include <cmath> 6 using namespace std; 7 8 const int maxn=105; 9 10 int x[maxn],y[maxn];11 int v[maxn*maxn],u[maxn*maxn];12 double w[maxn*maxn];13 int fa[maxn];14 int r[maxn*maxn];15 16 bool cmp (int x,int y){17 return w[x]<w[y];18 }19 20 int find (int x){21 if (fa[x]==x)22 return x;23 return fa[x]=find (fa[x]);24 }25 26 int main (){27 int t;28 scanf ("%d",&t);29 int n;30 while (t--){31 scanf ("%d",&n);32 for (int i=0;i<n;i++){33 scanf ("%d%d",&x[i],&y[i]);34 }35 int tot=0;36 for (int i=0;i<n;i++){37 for (int j=i+1;j<n;j++){38 int s=(x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]);39 if (s>=100&&s<=1000000){40 v[tot]=i;41 u[tot]=j;42 w[tot++]=100*sqrt (s*1.0);43 }44 }45 fa[i]=i;46 }47 for (int i=0;i<tot;i++)48 r[i]=i;49 int temp=0;50 sort (r,r+tot,cmp);51 double ans=0;52 for (int i=0;i<tot;i++){53 int fv=find(v[r[i]]);54 int fu=find(u[r[i]]);55 if (fv!=fu){56 ans+=w[r[i]];57 temp++;58 fa[fv]=fu;59 }60 }61 if (temp==n-1)62 printf ("%.1f\n",ans);63 else printf ("oh!\n");64 }65 return 0;66 }
HDU 1875 畅通工程再续
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。