首页 > 代码库 > 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 畅通工程再续