hdu 1233 还是畅通工程

点击打开链接hdu 1233

思路：最小生成树

分析：简单的最小生成树的题目，直接上模板

代码：

/*法一*/
#include<algorithm>
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define MAXN 10010

int n , m , ans;
int father[MAXN];
int rank[MAXN];
struct Edge{
     int x;
     int y;
     int value;
}e[MAXN];

bool cmp(Edge e1 , Edge e2){
     return e1.value < e2.value;
}

void Init_Set(){
     for(int i = 0 ; i <= n ; i++){
        father[i]  = i;
        rank[i] = 0;
     }
}

int Find_Set(int x){
     int tmp = x;
     while(father[tmp] != tmp)
          tmp = father[tmp];
     while(father[x] != tmp){
          int tmp_x = father[x];
          father[x] = tmp;
          x = tmp_x;
     }
     return tmp;
} 

void Union_Set(int x , int y){
     if(rank[x] >= rank[y]){
        rank[x] += rank[y];
        father[y] = x;
     }
     else{
        rank[y] += rank[x];
        father[x] = y;
     }
}

void solve(){ 
     Init_Set();
     sort(e , e+m , cmp);
     ans = 0;
     for(int i = 0 ; i < m ; i++){
        int root_x = Find_Set(e[i].x);
        int root_y = Find_Set(e[i].y);      
        if(root_x != root_y){         
          ans += e[i].value;
          Union_Set(root_x , root_y);
        }
     }
     printf("%d\n" , ans);
}

int main(){
    //freopen("input.txt" , "r" , stdin);
    while(scanf("%d" , &n), n){
        m = n*(n-1)/2;
        for(int i = 0 ; i < m ; i++)
           scanf("%d%d%d" , &e[i].x , &e[i].y , &e[i].value);
        solve();
    }
    return 0;
}

/*法二*/
#include<algorithm>
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define INF 0xFFFFFFF
#define MAXN 1010

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

void init(){
     for(int i = 1 ; i <= n ; i++){
        for(int j = 1 ; j <= n ; j++)
           G[i][j] = G[j][i] = INF;
     }
}

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

int main(){
    int x , y , v;
    while(scanf("%d" , &n) , n){
        init();
        m = n*(n-1)/2;
        for(int i = 0 ; i < m ; i++){
           scanf("%d%d%d" , &x , &y , &v);
           G[x][y] = G[y][x] = v;
        }
        Prime();
    }
    return 0;
}