zoj - 1406 - Jungle Roads

題意：有n個村莊，村莊間有一些路，但有一些路可以不要也可連通所有村莊，為節約費用，deal with一些不必要的路，求最少維護總費用。

——>>用Kruscal算法生成一棵最小生成樹，輸出即可。

[cpp] 
#include <iostream> 
#include <queue> 
#include <string.h> 
 
using namespace std; 
 
const int maxn = 30;        //1<n<27，開30夠了 
 
struct edge     //定義邊數據類型 
{ 
    int v1;     //邊的端點之一 
    int v2;     //邊的端點之一 
    int cost;       //一個月維護這條路的費用 
}; 
 
bool operator < (edge e1, edge e2)      //定義優先隊列排序方式 
{ 
    return (e1.cost > e2.cost); 
} 
 
int fa[maxn], height[maxn];     //fa[x]為x的父親，height[i]以i為根的樹的高度（並查集） 
int find(int x)     //找x的根（並查集） 
{ 
    while(fa[x] != x) 
    { 
        x = fa[x]; 
    } 
    return x; 
} 
 
bool judge(int x, int y)        //判斷加入邊x——y後是否會開成環，會的返回0，不會的話返回1 
{ 
    int new_x = find(x); 
    int new_y = find(y); 
    if(new_x == new_y) return 0;        //會形成環 
    else        //不會形成環 
    { 
        if(height[new_x] > height[new_y]) fa[new_y] = new_x; 
        else if(height[new_x] == height[new_y]) 
        { 
            fa[new_y] = new_x; 
            height[new_x]++; 
        } 
        else fa[new_x] = new_y; 
        return 1; 
    } 
} 
 
bool G[maxn][maxn];     //用鄰接矩陣來存儲圖 
bool vis[maxn], viss[maxn];         //vis、viss均用來判斷該村莊是否走過 
int n;      //n個村莊 
 
void dfs(int i)     //深度優先遍歷修改一個連通塊 
{ 
    vis[i] = 1; 
    int j; 
    for(j = 1; j <= n; j++) 
        if(G[i][j] == 1 && vis[j] == 0) 
            dfs(j); 
    return; 
} 
 
 
bool is_ok()        //判斷村莊是否已連通 
{ 
    memset(viss, 0, sizeof(viss)); 
    int count = 0, ok = 1, i; 
    for(i = 1; i <= n; i++) 
    { 
        if(viss[i] == 0) 
        { 
            dfs(i); 
            count++; 
            if(count >= 2) 
            { 
                ok = 0; 
                break; 
            } 
        } 
    } 
    if(ok) return 1; 
    else return 0; 
} 
 
int main() 
{ 
    int i, j; 
    while(cin>>n) 
    { 
        if(n == 0) return 0; 
        char c1, c2; 
        int num1, num2; 
        for(i = 1; i <= n; i++) 
        { 
            fa[i] = i; 
            height[i] = 1; 
        } 
 
        priority_queue<edge> qu;        //用優先隊列取最小費用的路徑 
 
        edge newnode; 
        memset(G, 0, sizeof(G)); 
        for(i = 1; i <= n-1; i++) 
        { 
            cin>>c1>>num1; 
            for(j = 1; j <= num1; j++) 
            { 
                cin>>c2>>num2; 
                G[(int)(c1-'A')+1][(int)(c2-'A')+1] = 1;        //把A,B,C...變成1,2,3... 
                G[(int)(c2-'A')+1][(int)(c1-'A')+1] = 1; 
                newnode.v1 = (int)(c1-'A')+1; 
                newnode.v2 = (int)(c2-'A')+1; 
                newnode.cost = num2; 
                qu.push(newnode);       //入列 
            } 
        } 
 
        int sum = 0;        //費用總數 
        int OK = 0;     //整個island是否連通的標志 
        memset(vis, 0, sizeof(vis)); 
        while(!OK && !qu.empty()) 
        { 
            if(judge(qu.top().v1, qu.top().v2))     //用並查集實現判斷加入那條邊是否會形成環，不會的時候 
            { 
                OK = 0; 
                vis[qu.top().v1] = 1;       //將這兩個村莊標記為已走 
                vis[qu.top().v2] = 1; 
                sum += qu.top().cost;       //累加總費用 
                if(is_ok()) OK = 1;     //加入此邊後判斷所有村莊是否已連通 
            } 
            qu.pop(); 
        } 
        cout<<sum<<endl; 
    } 
    return 0; 
}