HDU 1863 畅通工程(最小生成树，prim)

时间：2022-04-26 23:53:27

题意：

　　给出图的边和点数，要求最小生成树的代价，注：有些点之间是不可达的，也就是可能有多个连通图。比如4个点，2条边:1-2，3-4。

思路：

　　如果不能连通所有的点，就输出‘?’。之前以为每个点只要有边连着就一定能生成树，其实还可以是每个点虽然有边可达，但是给的其实是两个图，比如上例。其他按照常规Prim。

 #include <bits/stdc++.h>

 using namespace std;

 const int N=;

 const int mod=0x7f7f7f7f;

 int v[N][N];    //权

 int vis[N];

 int low[N];     //到每个点的最小权

 int prim(int n)

 {

     int pos=vis[]=;   //从点1开始

     for(int i=; i<=n; i++)   low[i]=v[][i]; //目前到每个点的最小权

     int ans=;

     for(int i=; i<n; i++)  //搞定另外n-1个点

     {

         int big=mod;

         for(int j=; j<=n; j++) //找权最小的边

         {

             if(!vis[j] && low[j]<big )  //未浏览过，目前可达，权小

             {

                 pos=j;

                 big=low[j];

             }

         }

         if(big==mod)    return ;   //无法到达。

         ans+=big;

         vis[pos]++; //浏览过

         for( int j=; j<=n; j++ )   //更新到每个点的权值

             if(!vis[j] && v[pos][j]<mod && low[j]>v[pos][j] ) low[j]=v[pos][j];    //未浏览过，有路可达,更短

     }

     return ans;

 }

 int main()

 {

     freopen("input.txt", "r", stdin);

     int n, m, a, b, t;

     while(scanf("%d%d", &n, &m), n)

     {

         memset(cnt,,sizeof(cnt));

         memset(vis,,sizeof(vis));

         memset(v,0x7f,sizeof(v));   //置为不可达

         for(int i=; i<n; i++)

         {

             scanf("%d%d%d",&a,&b,&t);

             v[a][b]=v[b][a]=t;

         }

         int ans=prim(m);

         if(ans)    printf("%d\n",ans);

         else  printf("?\n");

     }

     return ;

 }

AC代码

相关文章