(kruscal12.1.1)POJ 2421 Constructing Roads(使用kruscal算法来生成最小生成树&&计算最小带权路径和)

 
/* 
 * POJ_2421.cpp 
 * 
 *  Created on: 2013年11月8日 
 *      Author: Administrator 
 */  
  
  
#include   
#include   
#include   
#include   
  
  
using namespace std;  
  
struct edge{  
    int begin;  
    int end;  
    int weight;  
};  
  
const int maxn = 110;  
int father[maxn];  
edge e[maxn*maxn];  
int map[maxn][maxn];  
  
int find(int x){  
    if( x == father[x]){  
        return x;  
    }  
  
    father[x] = find(father[x]);  
    return father[x];  
}  
  
int kruscal(int count){//使用kruscal算法来生成最小生成树并计算带权路径和  
    int i;  
    int sum = 0;//用sum来记录最小s生成树的边权和  
  
    for( i = 1 ; i < maxn ; ++i){  
        father[i] = i;  
    }  
  
    for( i = 0 ; i < count ; ++i){//枚举有序边集中的每一条边  
        int fx = find(e[i].begin);  
        int fy = find(e[i].end);  
  
        if(fx != fy){//若第k条边的两个端点i,j 分别属于两颗不同的子树  
            father[fx] = fy;//则将节点i所在的子树并入节点j所在的子树中  
            sum += e[i].weight;  
        }  
    }  
  
    return sum;  
}  
  
bool compare(const edge& a , const edge& b){  
    return a.weight < b.weight;  
}  
  
//以上是用kruscal算法来解决问题的基本模板.....  
  
int main(){  
    int n;  
    while(scanf("%d",&n)!=EOF){  
  
        int i,j;  
        for(i = 1 ; i <= n ; ++i){  
            for(j = 1 ; j <= n ; ++j){  
                scanf("%d",&map[i][j]);  
            }  
        }  
  
        int m;  
        scanf("%d",&m);  
        while(m--){  
            int a,b;  
            scanf("%d%d",&a,&b);  
            map[a][b] = map[b][a] =0;//将已有边的权值设为0  
        }  
  
        int count = 0;  
        for(i = 1 ; i <= n ; ++i){//距离矩阵的处理方式  
            for(j = i+1 ; j <= n ; ++j){  
                e[count].begin = i;  
                e[count].end = j;  
                e[count++].weight = map[i][j];  
            }  
        }  
  
        sort(e,e+count,compare);//kruscal算法要求边有序  
  
        int sum = kruscal(count);  
  
        printf("%d\n",sum);  
    }  
  
    return 0;  
}