Linux安全网 - Linux操作系统_Linux 命令_Linux教程_Linux黑客

会员投稿 投稿指南 本期推荐:
搜索:
您的位置: Linux安全网 > Linux编程 > » 正文

poj-2421 Constructing Roads *

来源: 未知 分享至:
/*
* 蛮水的一道MST Kruskal, 链表实现
*
* 预处理:
* 根据已有的边,把相应的集合合并。。再Kruskal
*
* 另一种方法:
* 把已有边的权值改为0
*
*/
#include
<cstdio>
#include
<algorithm>
using namespace std;

const int maxN = 100 + 5;
int n, totEdgeNum, G[maxN][maxN], q, ans;

struct SEdge{
int w, u, v;
};
SEdge edge[maxN
* maxN];

struct SNode{
int num, len;
SNode
*rep, *next;
};
SNode
*head[maxN], *tail[maxN], *node[maxN];

SNode
* makeSet(SNode *x){
head[x
->num] = x; tail[x->num] = x;
x
->rep = x; x->next = NULL;
x
->len = 1;

return x;
}
SNode
* findSet(SNode *x){
return x->rep;
}
SNode
* unionSet(SNode *lhs, SNode *rhs){
SNode
*first, *second, *cur;
if(lhs->rep->len >= rhs->rep->len){
first
= lhs->rep; second = rhs->rep;
}
else{
first
= rhs->rep; second = lhs->rep;
}

cur
= second;
while(cur != NULL){
cur
->rep = first;
cur
= cur->next;
}
tail[first
->num]->next = head[second->num];
tail[first
->num] = tail[second->num];
head[second
->num] = head[first->num];

return first;
}

int cmp(const void *lhs, const void *rhs){
SEdge
*a = (SEdge *)lhs; SEdge *b = (SEdge *)rhs;
return a->w - b->w;
}

void mstKruskal(){
qsort(edge, totEdgeNum,
sizeof(SEdge), cmp);

/*
for(int i=0; i<totEdgeNum; i++){
printf(\"%d \", edge[i].w);
}
printf(\"n\");
*/


for(int i=0; i<totEdgeNum; i++){
if(findSet(node[edge[i].u]) != findSet(node[edge[i].v])){
ans
+= edge[i].w;

Tags:
分享至:
最新图文资讯
1 2 3 4 5 6
验证码:点击我更换图片 理智评论文明上网,拒绝恶意谩骂 用户名:
关于我们 - 联系我们 - 广告服务 - 友情链接 - 网站地图 - 版权声明 - 发展历史