[cpp] view plaincopyprint?
/*
* 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;
}
阅读(772) | 评论(0) | 转发(0) |