hdu 1863 畅通工程

点击打开链接hdu 1863

1思路：最小生成树+Prime

2注意：n是边数，m是点数。当m为0的时候输出的数“?”。

代码：

#include<algorithm>
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define MAXN 110
#define INF 0xFFFFFFF

int n , m;
long long ans;
long long G[MAXN][MAXN];
int vis[MAXN];
long long lowcost[MAXN];

/*判断是否满足*/
bool judge(){
     for(int i = 1 ; i <= m ; i++){
        if(!vis[i])
          return false;
     }  
     return true;
}

/*初始化点之间的距离为无穷大*/
void init(){
     for(int i = 1 ; i <= m; i++){
          for(int j =1 ; j <= m ; j++)
               G[i][j] = INF;
     }
}

void Prime(){
     int i , j , pos , flag;
     long long min;
     memset(vis , 0 , sizeof(vis));
     vis[1] = 1;
     ans = 0;
     for(i = 1 ; i <= m ; i++)
        lowcost[i] = G[1][i];
     for(i = 1 ; i <= m ; i++){
        min = INF;
        for(j = 1 ; j <= m ; j++){
           if(!vis[j] && lowcost[j] < min){
              min = lowcost[j];
              pos = j;
           } 
        }
        if(min == INF)
           break;
        ans += min;
        vis[pos] = 1;
        for(j = 1 ; j <= m ; j++){
           if(!vis[j] && lowcost[j] > G[pos][j])
              lowcost[j] = G[pos][j];
        }
     }
     if(judge())
       printf("%lld\n" , ans);
     else
       printf("?\n");
} 

int main(){
   // freopen("input.txt" , "r" , stdin);
    int a, b , c;
    while(scanf("%d%d" , &n , &m) && n){
         init();
         for(int i = 1 ; i <= n ; i++){
             scanf("%d%d%d" , &a , &b , &c);
             G[a][b] = G[b][a] = c;
         }
         if(m)
           Prime();
        else
           printf("?\n"); 
    }
    return 0;
}