首页 > 代码库 > Ural 1982 Electrification Plan (prim最小生成树)

Ural 1982 Electrification Plan (prim最小生成树)

2024-07-17 05:05:39   212人阅读

很明显的最小生成树模板题 多点生成

[cpp] view plaincopy在CODE上查看代码片派生到我的代码片
  1. #include<bits/stdc++.h>  
  2. using namespace std;  
  3. int n,k,a;  
  4. int dist[120],m[120][120];  
  5. bool p[120];  
  6. void prim()  
  7. {  
  8.     for(int i=1;i<=n;i++)  
  9.     {  
  10.         if(!p[i])  
  11.         {  
  12.             int Min=100020;  
  13.             for(int j=1;j<=n;j++)  
  14.             {  
  15.                 if(p[j]&&m[i][j]<Min)  
  16.                     Min=m[i][j];  
  17.             }  
  18.             dist[i]=Min;  
  19.         }  
  20.     }  
  21.     for(int i=1;i<=n-k;i++)  
  22.     {  
  23.         int Min=INT_MAX,k=0;  
  24.         for(int j=1;j<=n;j++)  
  25.         {  
  26.             if(!p[j]&&dist[j]<Min)  
  27.             {  
  28.                 Min=dist[j];  
  29.                 k=j;  
  30.             }  
  31.         }  
  32.         if(k==0)  
  33.             return;  
  34.         p[k]=true;  
  35.         for(int j=1;j<=n;j++)  
  36.         {  
  37.             if(!p[j]&&dist[j]>m[k][j])  
  38.                 dist[j]=m[k][j];  
  39.         }  
  40.     }  
  41. }  
  42. int main()  
  43. {  
  44.     memset(p,false,sizeof(p));  
  45.     scanf("%d%d",&n,&k);  
  46.     for(int i=1;i<=k;i++)  
  47.     {  
  48.         scanf("%d",&a);  
  49.         dist[a]=0;  
  50.         p[a]=true;  
  51.     }  
  52.     for(int i=1;i<=n;i++)  
  53.         for(int j=1;j<=n;j++)  
  54.             scanf("%d",&m[i][j]);  
  55.     prim();  
  56.     int sum=0;  
  57.     for(int i=1;i<=n;i++)  
  58.         sum+=dist[i];  
  59.     printf("%d\n",sum);  
  60.     return 0;  
  61. } 


联系
我们