/* THE PROGRAM IS MADE BY PYY */
/*----------------------------------------------------------------------------//
Copyright (c) 2012 panyanyany All rights reserved.
URL : http://acm.hdu.edu.cn/showproblem.php?pid=1879
Name : 1879 继续畅通工程
Date : Monday, February 6, 2012
Time Stage : half an hour
Result:
5320539 2012-02-06 10:34:06 Accepted 1879
281MS 236K 2326 B
C++ pyy
Test Data :
Review :
出了很多错啊
//----------------------------------------------------------------------------*/
#include <cstdio>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
using namespace std ;
#define MEM(a, v) memset (a, v, sizeof (a)) // a for address, v for value
#define max(x, y) ((x) > (y) ? (x) : (y))
#define min(x, y) ((x) < (y) ? (x) : (y))
#define INF (0x3f3f3f3f)
#define MAXN (103)
#define MAXE (MAXN*(MAXN-1)/2)
#define DEBUG /##/
struct EDGE {
int u, v, w ;
bool operator< (const EDGE &e) {
return w < e.w ;
}
};
int n, m, edgeCnt ;
int set[MAXN] ;
int map[MAXN][MAXN] ;
EDGE edge[MAXE] ;
void init_kruskal()
{
int i ;
for (i = 1 ; i <= n ; ++i)
set[i] = i ;
edgeCnt = 0 ;
}
int find (int x)
{
if (x == set[x])
return x ;
return set[x] = find(set[x]) ;
}
inline void merge (int x, int y)
{
set[x] = set[y] ;
}
int kruskal ()
{
int i, sum ;
sort (edge, edge+m) ;
sum = 0 ; // 没初始化,WA
for (i = 0 ; i < m ; ++i)
{
if (n-1 <= edgeCnt) //这里的话,<= 和 == 在hdu结果是一样的
break ;
int x = find (edge[i].u) ;
int y = find (edge[i].v) ;
if (x != y)
{
merge (x, y) ;
++edgeCnt ;
sum += edge[i].w ;
}
}
return sum ;
}
int main ()
{
int i, b ;
while (scanf ("%d", &n), n)
{
m = n*(n-1)/2 ;
// 初始化,跟之前的模板题不同,这题要先初始化(个人的想法)
init_kruskal() ;
for (i = 0 ; i < m ; ++i)
{
scanf ("%d%d%d%d", &edge[i].u, &edge[i].v, &edge[i].w, &b) ;
if (b) //对于已经建成的路,就检查是否在集合中
{
int x = find(edge[i].u) ;
int y = find(edge[i].v) ;
if (x != y) //若不在同一个集合,就合并集合
{
merge (x, y) ;
++edgeCnt ; // 别忘了边数也要递增
}
--i, --m ; // 放到了 find(edge[i].u) 前面,WA
}
}
printf ("%d\n", kruskal()) ;
}
return 0 ;
}
分享到:
相关推荐
编写算法能够建立带权图,并能够用Kruskal算法求该图的最小生成树。最小生成树能够选择图上的任意一点做根结点。最小生成树输出采用顶点集合和边的集合的形式。
代码 最小生成树Kruskal算法代码代码 最小生成树Kruskal算法代码代码 最小生成树Kruskal算法代码代码 最小生成树Kruskal算法代码代码 最小生成树Kruskal算法代码代码 最小生成树Kruskal算法代码代码 最小生成树...
该程序是我写的博客“一起talk C栗子吧(第五十回:C语言实例--最小生成树二)”的配套程序,共享给大家使用
代码 最小生成树kruskal算法离散型优化问题代码代码 最小生成树kruskal算法离散型优化问题代码代码 最小生成树kruskal算法离散型优化问题代码代码 最小生成树kruskal算法离散型优化问题代码代码 最小生成树kruskal...
最小生成树kruskal算法 最小生成树kruskal算法
matlab程序 最小生成树 matlab Kruskal 源代码
实现了kruskal的算法,测试可行。
我自己编写的一个C++ kruskal最小生成树程序,希望可以对初学者有所帮助,错误难以避免,希望大家谅解
第3关求图(邻接矩阵存储)最小生成树的克鲁斯卡尔(Kruskal)算法 第4关求图(邻接表存储)最小生成树的克鲁斯卡尔(Kruskal)算法 稳过 生成树是将图中所有顶点以最少的边连通的子图。权值和最小的生成树就是最小...
数据结构课程设计报告最小生成树Kruskal算法
最小生成树Kruskal算法[定义].pdf
最小生成树_kruskal
求最小生成树 求最小生成树 求最小生成树 求最小生成树 求最小生成树 求最小生成树 求最小生成树
最小生成树的kruskal算法(c++源码)
建立一个图,其存储方式采用邻接矩阵形式,利用普里姆算法和克鲁斯卡尔算法求网的最小生成树,按顺序输出生成树中各条边以及它们的权值。
图论- 生成树- 最小生成树- Kruskal.rar
利用krustra算法实现图的最小生成树
利用matlab 编写的kruskal 最小生成树的算法。
对给定的图结构,实现求解最小生成树的Kruskal算法。每次在满足和已选边不构成回路的条件下选择一条权植最小的边,添加到新的生成数中。Kruskal算法的实现类似于计算连通枝的算法。它使用了分离集合数据结构以保持数...
最小生成树kruskal算法并查集版+C语言实现