HDU4463(最小生成树)

悠悠 2021-12-24 14:37 163阅读 0赞

模版稍微改一下，Prime在搜到其中一个点时直接把另一条边加入即可。

代码如下：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include <iostream>
     2 #include <cstdio>
     3 #include <cstring>
     4 #include <cmath>
     5 #define LEN 110
     6 #define INF 0x7fffffff
     7 using namespace std;
     8 
     9 int n;
    10 typedef struct {
    11     int x, y;
    12 }POINT;
    13 
    14 POINT store[LEN];
    15 int ta, tb;
    16 double map[LEN][LEN], dis[LEN];
    17 int vis[LEN];
    18 
    19 double prime(int vex)
    20 {
    21     double sum = 0;
    22     memset(vis, 0, sizeof vis);
    23     memset(dis, 0, sizeof dis);
    24     vis[0]=1;
    25     for(int i=0; i<n; i++)
    26         dis[i] = map[vex][i];
    27     for(int i=0; i<n-1; i++)
    28     {
    29         int min;
    30         double minsize = INF;
    31         if(vis[ta]+vis[tb]==1){
    32             minsize = map[ta][tb];
    33             min = ((i==ta)?tb:ta);
    34             vis[min] = 1;
    35             sum += minsize;
    36             for(int j=0; j<n; j++)
    37                 if(map[min][j]<dis[j])
    38                     dis[j] = map[min][j];
    39         }
    40         else{
    41             for(int j=0; j<n; j++){
    42                 if(minsize>dis[j] && vis[j]==0){
    43                     min = j;
    44                     minsize = dis[j];
    45                 }
    46             }
    47             vis[min] = 1;
    48             sum += minsize;
    49             for(int j=0; j<n; j++)
    50                 if(map[min][j]<dis[j])
    51                     dis[j] = map[min][j];
    52         }
    53     }
    54     return sum;
    55 }
    56 
    57 double Dis(POINT a, POINT b)
    58 {
    59     return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
    60 }
    61 
    62 void build()
    63 {
    64     scanf("%d%d", &ta, &tb);
    65     ta--;tb--;
    66     for(int i=0; i<n; i++){
    67         scanf("%d%d", &store[i].x, &store[i].y);
    68     }
    69     for(int i=0; i<n; i++)
    70     for(int j=0; j<n; j++){
    71         map[i][j] = Dis(store[i], store[j]);
    72     }
    73 }
    74 
    75 int main()
    76 {
    77 //    freopen("in.txt", "r", stdin);
    78 
    79     while(scanf("%d", &n)!=EOF && n)
    80     {
    81         build();
    82         printf("%.2lf\n", prime(0));
    83     }
    84     return 0;
    85 }

转载于:https://www.cnblogs.com/shu-xiaohao/p/3383784.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211223/574e6af2aa7245ca80b952374d46bf4b.png