http://acm.hdu.edu.cn/showproblem.php?pid=1863
/*
kruskal算法:
先把所有路线按权值排序,然后从小到大遍历每一条路线,如果路线的两端尚没有连通,就把该路线连通,并更新已连通路线的长度和数目,最后如果”已连通路线数目=端点数-1”则已连通路线长度为最小生成树。
*/
#include<stdio.h>
#include<stdlib.h>
int set[105],flag;
struct road
{
int a;
int b;
int value;
}s[5000];
int cmp(const void*a,const void*b)
{
return (*(struct road*)a).value-(*(struct road*)b).value;
}
int Findset(int x)
{
if(x!=set[x])
set[x]=Findset(set[x]);
return set[x];
}
void Unionset(int a,int b)
{
int x=Findset(a);
int y=Findset(b);
if(x==y)
return;
set[y]=x;
flag=1;
}
int main()
{
int n,m,i,t,sum;
while(scanf("%d%d",&n,&m),n)
{
for(i=1;i<=n;i++)
set[i]=i;
sum=0;t=0;
for(i=0;i<n;i++)
scanf("%d%d%d",&s[i].a,&s[i].b,&s[i].value);
qsort(s,n,sizeof(s[0]),cmp);
for(i=0;i<n;i++)
{
flag=0;
Unionset(s[i].a,s[i].b);
if(flag)
{
sum+=s[i].value;
t++;
}
}
if(t==m-1)
printf("%d\n",sum);
else
printf("?\n");
}
return 0;
}
/*
prim算法:
先任意确定一个点标记为已访问,然后每次找到已访问点集与其余集之间的最短距离,连通该路线,并将路线终点标记为已访问。直到所有点都标记为已访问。
prim算法与dijkstra算法(计算最短路)非常相似。注意它们的区别:
prim算法中找到的最短距离是已访问点集与其余集之间的最短距离,而dijkstra算法中的最短距离是起点到未访问点集的最短距离。prim算法可以将已访问的点的距离值置0表示已访问过,而dijkstra算法需另外开一个数组记录是否访问。
*/
#include<stdio.h>
#include<stdlib.h>
#define M 102
#define Max 100000000
int map[M][M],value[M],m,sum,cnt;
void Prim()
{
int i,j,k,min;
cnt=1;
sum=0;
for(i=1;i<=m;i++) //初始化value[]
value[i]=map[1][i];
for(i=1;i<=m;i++){
min=Max;
for(j=1;j<=m;j++){ //找到当前最小支
if(value[j]!=0&&value[j]<min){
min=value[j];
k=j;
}
}
if(min==Max||cnt==m)break;
sum+=min;
cnt++;
value[k]=0;
for(j=1;j<=m;j++){ //更新value[]
if(value[j]!=0&&value[j]>map[k][j]) //value[j]记录已走过的点到点j的最短距离
value[j]=map[k][j];
}
}
}
int main()
{
int i,j,n,a,b,c;
while(scanf("%d%d",&n,&m),n){
for(i=1;i<=m;i++){
for(j=1;j<=m;j++)
map[i][j]=(i==j?0:Max);
}
for(i=1;i<=n;i++){
scanf("%d%d%d",&a,&b,&c);
map[a][b]=map[b][a]=min(map[a][b],c);
}
Prim();
if(cnt==m)
printf("%d\n",sum);
else
printf("?\n");
}
return 0;
}
分享到:
相关推荐
杭电ACM课件2014版之 (HDUACM201403版_06)并查集(最小生成树)
HDUACM201509版_07并查集(最小生成树).ppt文件很可能包含了关于这个问题的详细讲解,包括并查集的建立、维护以及如何与Kruskal算法结合来求解最小生成树的问题。 并查集是一种用于处理连接关系的数据结构,它可以...
(HDUACM2010版_06)并查集(最小生成树(HDUACM2010版_06)并查集(最小生成树(HDUACM2010版_06)并查集(最小生成树(HDUACM2010版_06)并查集(最小生成树
本分类涵盖了图论领域的多种类型的题目,涉及到图论的基本概念、图的遍历、图的搜索、图的匹配、图的.isConnected性、图的最短路径、图的最小生成树、图的拓扑排序等多个方面。 图论是一个重要的计算机科学领域,...
3. **数据结构**:数组、链表、栈、队列、树(二叉树、平衡树如AVL和红黑树)、图(邻接矩阵、邻接表、最小生成树、拓扑排序等)。 4. **字符串处理**:KMP算法、Manacher's Algorithm、Rabin-Karp算法等。 5. **...
4. **最小生成树**:在图论中,最小生成树是连接所有顶点的边权之和最小的树。经典的算法有Prim算法和Kruskal算法,它们分别基于加边和加边的原则找到最小生成树。 5. **搜索**:搜索算法在ACM中至关重要,包括深度...
8. **图论与树**:HDU题目中可能涉及图的遍历(深度优先搜索DFS、广度优先搜索BFS)、树的遍历(前序、中序、后序)以及最小生成树、最短路径等算法。 9. **动态规划**:这是一种优化策略,通过构建状态转移方程来...
通常这类问题会要求程序员设计算法来寻找图中最小生成树或最短路径,以优化网络流量或资源分配。 在图论中,最小生成树(Minimum Spanning Tree, MST)是指一个无向图中,所有顶点间边的集合,这个集合构成了一棵树...
1. **基础算法**:包括排序(快速排序、归并排序等)、搜索(二分查找、深度优先搜索等)、图论(最短路径、最小生成树等)。 2. **动态规划**:解决许多具有重叠子问题和最优子结构的问题,如背包问题、最长公共子...
4. **图论算法**:最短路径算法(Dijkstra、Floyd-Warshall)、拓扑排序、最小生成树(Prim、Kruskal)等。 5. **数学方法**:模运算、数论、组合数学等。 6. **字符串处理**:KMP匹配、Z算法、后缀数组、AC自动机等...
1. **基础算法**:包括排序算法(快速排序、归并排序、堆排序等)、搜索算法(深度优先搜索、广度优先搜索、A*搜索等)、图论算法(最短路径、最小生成树、拓扑排序等)和动态规划等。 2. **数据结构**:如链表、...
- 贪心算法:通过局部最优解来寻找全局最优解,如霍夫曼编码、 Prim's最小生成树算法等。 - 回溯法:在搜索过程中遇到无效解时回退一步,常用于解决组合优化问题,如八皇后问题、数独等。 3. 数学与理论篇: - ...
这些算法在解决实际问题时起着关键作用,比如寻找最短路径、最大子序列和、最小生成树等。 针对杭电HDU的题目,很可能需要运用到上述的一种或多种数据结构和算法。例如,一道题目可能要求实现一个高效的查找算法,...
5. **图论**:图的遍历(深度优先搜索DFS和广度优先搜索BFS)、最小生成树(Prim和Kruskal算法)、最短路径(Dijkstra和Floyd算法)等。在解决网络问题、旅行商问题等时,图论知识至关重要。 6. **递推和动态规划**...
3. (HDUACM2010版_06)并查集(最小生成树).ppt:这是一个PPT文件,可能详细介绍了如何使用并查集来求解最小生成树的问题,包括理论知识、算法流程和示例解析。 4. hdoj1829二分图识别的并查集.txt:二分图是图论...
10. **图论问题**:包括最小生成树(Prim算法和Kruskal算法)、最短路径(Dijkstra算法和Bellman-Ford算法)、网络流(Ford-Fulkerson算法和Edmonds-Karp算法)等。 通过深入学习和实践这些解题报告,不仅可以提升...
2. **高级算法**:除了基础算法,ACM培训可能会深入到更复杂的算法,如字符串匹配算法、回溯法、分治法、最小生成树、最短路径算法等,这些都是解决复杂问题的关键。 3. **编程语言**:大多数ACM竞赛使用C++或Java...
5. **算法**:报告涵盖的算法可能包括排序(快速排序、归并排序、冒泡排序等)、查找(二分查找、哈希查找)、图论算法(最短路径、最小生成树)、组合数学(排列组合、鸽巢原理、容斥原理)等。 6. **编程技巧**:...
1. **基础算法**:这是ACM编程的基础,包括排序(快速排序、归并排序、堆排序等)、搜索(二分查找、深度优先搜索、广度优先搜索)、图论(最短路径算法如Dijkstra和Floyd-Warshall,最小生成树如Prim和Kruskal)等...
9. **图的搜索算法应用**:搜索算法在图论中有广泛应用,如拓扑排序、最小生成树、最短路径等。掌握这些算法对于解决实际问题至关重要。 10. **实践与技巧**:在ACM竞赛中,除了理解理论知识,还需要熟练掌握算法的...