hdu 3405 删掉某点后求最小生成树

给出N个点的坐标边的权值为两点间的距离删掉其中某点求最小生成树的权值和要求这权值最小

因为最多50个点所以具体是删哪个点用枚举
假如有4个点就要求4次最小生成树分别是2 3 4 | 1 3 4 | 1 2 4 | 1 2 3 这些点的

Sample Input
2
5
0 0
1 0
18 0
0 1
1 1
3
0 0
1 0
0 1

Sample Output
3.00
1.00

prim

 1 # include <iostream>
 2 # include <cstdio>
 3 # include <cstring>
 4 # include <algorithm>
 5 # include <cmath>
 6 # define LL long long
 7 using namespace std ;
 8 
 9 const int INF=0x3f3f3f3f;
10 const int MAXN=110;
11 bool vis[MAXN];
12 double lowc[MAXN];
13 double cost[MAXN][MAXN] ;
14 
15 struct poin
16 {
17     int x ;
18     int y ;
19 }p[110] , q[110];
20 
21 double Prim(int n)
22 {
23     int i , j ;
24     for (i = 0 ; i < n ; i++)
25         for (j = 0 ; j < n ; j++)
26             cost[i][j] = INF ;
27     for (i = 0 ; i < n ; i++)
28             for (j = i+1 ; j < n ; j++)
29             {
30                 double t = sqrt((double)(q[i].x - q[j].x) * (q[i].x - q[j].x) + (q[i].y - q[j].y) * (q[i].y - q[j].y)) ;
31                 cost[i][j] = t ;
32                 cost[j][i] = t ;
33             }
34     double ans=0;
35     memset(vis,false,sizeof(vis));
36     vis[0]=true;
37     for(int i=1;i<n;i++)lowc[i]=cost[0][i];
38     for(int i=1;i<n;i++)
39     {
40         double minc=INF;
41         int p=-1;
42         for(int j=0;j<n;j++)
43             if(!vis[j]&&minc>lowc[j])
44             {
45                 minc=lowc[j];
46                 p=j;
47             }
48             if(minc==INF)return -1;//原图不连通
49             ans+=minc;
50             vis[p]=true;
51             for(int j=0;j<n;j++)
52                 if(!vis[j]&&lowc[j]>cost[p][j])
53                     lowc[j]=cost[p][j];
54     }
55     return ans;
56 }
57 
58 int main()
59 {
60 
61    // freopen("in.txt","r",stdin) ;
62     int T ;
63     scanf("%d" , &T) ;
64     while(T--)
65     {
66         int n ;
67         scanf("%d" , &n) ;
68         int i , j ;
69         double MIN = INF ;
70         for (i = 0 ; i < n ; i++)
71             scanf("%d %d" , &p[i].x , &p[i].y) ;
72 
73         for (i = 0 ; i < n ; i++)
74         {
75             int k = 0 ;
76             for (j = 0 ; j < n ; j++)
77             {
78                if (i == j)
79                   continue ;
80                q[k].x = p[j].x ;
81                q[k].y = p[j].y ;
82                k++ ;
83             }
84             double ans = Prim(n-1) ;
85             if (ans < MIN)
86                 MIN = ans ;
87         }
88         printf("%.2lf
" , MIN) ;
89 
90     }
91     return 0 ;
92 }

View Code

hdu 3405 删掉某点后 求最小生成树

hdu 3405 删掉某点后求最小生成树