poj1258 Agri-Net

标签：最小生成树

/*    题意：给出n*n的无向图的邻接矩阵，输出最小生成树的权值和。    思路：Kruskal。    优化：无向图矩阵是对称的，只保存上三角。到最后k的值就是边数，由循环n*n-->k次。*/#include 
   
    #include 
    
     using namespace std;#define maxn 105typedef struct{    int x, y;    int w;}edge;edge e[maxn * maxn / 2];int rank_[maxn], father[maxn], sum;int cmp(edge a, edge b){  //按权值非降序排序    return a.w < b.w;}void make_set(int x){    father[x] = x;    rank_[x] = 0;}int find_set(int x){    return  x != father[x] ? find_set(father[x]) : father[x];}void union_set(int x, int y, int w){    if(x == y)  return ;    if(rank_[x] > rank_[y])  father[y] = x;    else{        if(rank_[x] == rank_[y])  rank_[y]++;        father[x] = y;    }    sum += w;  //}int main(){    int n, k, i, j, no;    while(scanf("%d", &n) != EOF){        k = 0, sum = 0;        for(i = 0; i < n; i++){            make_set(i);            for(j = 0; j < n; j++)                if(j < i){  //只读取下三角                    e[k].x = i, e[k].y = j;                    scanf("%d", &e[k++].w);                }                else  scanf("%d", &no);        }        sort(e, e + k, cmp);        for(i = 0; i < k; i++)  union_set(find_set(e[i].x), find_set(e[i].y), e[i].w);        printf("%d\n", sum);    }    return 0;}

转载地址：http://kskxi.baihongyu.com/

你可能感兴趣的文章