HDU 1875 畅通工程再续（Kruscal最小生成树）

秒速五厘米 2021-12-20 14:09 324阅读 0赞

文章作者：ktyanny 文章来源：[ktyanny][] 转载请注明，谢谢合作。

ktyanny：好吧，中文题目了，那么题目描述就不多说了。一看就是用最小生成树的思想来解决的。这个题目没有1Y很可惜的一点是开始用的是float来做，WA了，把类型改为double就AC了，囧了一下……

312MS C++

/\*   
by ktyanny  
2009.12.15  
 \*/   
\#include  < stdio.h >   
\#include  < stdlib.h >   
\#include  < string .h >   
\#include  < math.h >   
\#include  < iostream >   
 using  namespace  std;  
  
 const  int  MAX  =  105 ;  
  
typedef  struct   
\{  
 int  x, y;  
 double  w;  
\}edge;  
 const  int  MAXN  =  50005 ;  
edge e\[MAXN\];  
 double  ans;  
  
 int  rank\[MAXN\];  
 int  pa\[MAXN\];  
  
 void  make\_set( int  x)  
\{  
pa\[x\]  =  x;  
rank\[x\]  =  0 ;  
\}  
  
 int  find\_set( int  x)  
\{  
 if (x  !=  pa\[x\])  
pa\[x\]  =  find\_set(pa\[x\]);  
 return  pa\[x\];  
\}  
  
 /\* 按秩合并x，y所在的集合 \*/   
 void  union\_set( int  x,  int  y,  double  w)  
\{  
x  =  find\_set(x);  
y  =  find\_set(y);  
 if (x  ==  y) return  ;  
ans  \+=  w;  
 if (rank\[x\]  >  rank\[y\]) /\* 让rank比较高的作为父结点 \*/   
\{  
pa\[y\]  =  x;  
\}  
 else   
\{  
pa\[x\]  =  y;  
 if (rank\[x\]  ==  rank\[y\])  
rank\[y\] \++ ;  
\}  
\}  
  
  
 int  cmp( const  void  \* a,  const  void  \* b)  
\{  
 return  ( ( \* (edge  \* )a).w  >  ( \* (edge  \* )b).w )  ?  1  :  \- 1 ;  
\}  
  
typedef  struct   
\{  
 double  xx, yy;  
\}point;  
  
point P\[ 105 \];  
 int  main()  
\{  
 int  n, i, j, jj,k, x, y, t, m;  
 char  ch1, ch2;  
cin  >>  m;  
 while (m \-- )  
\{  
cin  >>  n;  
j  =  0 ;  
 for (i  =  1 ; i  <=  n; i \++ )  
cin  >>  P\[i\].xx  >>  P\[i\].yy;  
  
 /\* 处理图的边集 \*/   
 double  temp;  
 for (i  =  1 ; i  <=  n; i \++ )  
\{  
 for (k  =  i; k  <=  n; k \++ )  
\{  
temp  =  sqrt((P\[i\].xx \- P\[k\].xx) \* (P\[i\].xx \- P\[k\].xx)  \+  (P\[i\].yy \- P\[k\].yy) \* (P\[i\].yy \- P\[k\].yy) );  
 if (temp  <  10  ||  temp  >  1000 )  
 continue ;  
 else   
\{  
e\[j\].w  =  temp;  
e\[j\].x  =  i;  
e\[j\].y  =  k;  
j \++ ;  
\}  
\}  
\}  
  
 for (i  =  0 ; i  <=  n; i \++ )  
make\_set(i);  
  
qsort(e, j,  sizeof (e\[ 0 \]), cmp);  
  
 /\* Kruscal过程求最小生成树 \*/   
ans  =  0.0 ;  
 for (i  =  0 ; i  <  j; i \++ )  
\{  
x  =  find\_set(e\[i\].x);  
y  =  find\_set(e\[i\].y);  
 if (x  !=  y)  
union\_set(x, y, e\[i\].w);  
\}  
 if (ans  >  0 )\{  
ans  \*=  100 ;  
printf( " %.1lf\\n " , ans);  
\}  
 else  printf( " oh!\\n " );  
\}  
 return  0 ;  
\}

转载于:https://www.cnblogs.com/ktyanny/archive/2009/12/15/1625049.html

[ktyanny]: http://www.cnblogs.com/ktyanny/