注册 登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

zorksylar

Nothing is impossible , if distributed.

 
 
 

日志

 
 

【图论】【最小生成树】【kruscal + disjoint_sets】 POJ 1258 Agri-Net  

2011-09-23 22:12:16|  分类: ACM_图论 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
题目连接:
题目大意:
给你n个农场及它们间的距离,求把所有农场联系起来的最短距离

分析:
裸最小生成树,kruscal 主要是贪心+并查集思想,找最小权值的边一次添加到最小生成树,但加边的时候需要考虑不能构成环,此时需要并查集判断是否存在环
my first MST blood

代码:

#include <cstdio>
#include <algorithm>

using namespace std;

const int MAXN = 110;
int n;
int mat[MAXN][MAXN];
struct Edge
{
        int u;
        int v;
        int w;
};

Edge edge[MAXN*MAXN];
int edge_cont;

int rank[MAXN];
int father[MAXN];

void makeset(int x)
{
        father[x] = x;
        rank[x] = 0;
}

int findset(int x)
{
        if(father[x] != x) father[x] = findset(father[x]);
        return father[x];
}

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

void unin(int x,int y)
{
        link(findset(x),findset(y));
}

bool mcmp(Edge x,Edge y)
{
        return x.w < y.w;



void init()
{
        edge_cont = 0;
        int i,j;
        int td;
        for(i = 1;i <= n;i ++)
        {
                for(j = 1;j <= n;j ++)
                {        
                        scanf("%d",&td);
                        if(i != j)
                        {
                                edge[edge_cont].u = i;
                                edge[edge_cont].v = j;
                                edge[edge_cont].w = td;
                                edge_cont ++;
                        }
                }
        }

        for(i = 1;i <=n; i++)
        {
                makeset(i);
        }

        stable_sort(edge,edge+edge_cont,mcmp);
}


void work()
{
        int ans = 0;
        int i;
        int tx;
        int ty;
        int ncont = 0;

        for(i = 0;i < edge_cont;i ++)
        {
                tx = findset(edge[i].u);
                ty = findset(edge[i].v);
                if(tx != ty)
                {
                        link(tx,ty);
                        ans += edge[i].w;
                        ncont ++;
                        if(ncont >= n-1) break;
                }
        }
        
        printf("%d\n",ans);
}


int main()
{
        while(scanf("%d",&n) != EOF)
        {
                init();
                work();
        }
        return 0;
}

  评论这张
 
阅读(166)| 评论(2)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018