首页 > 代码库 > 北大 2012 Jungle Roads
北大 2012 Jungle Roads
题目：
输入边的两端点和边值，求最小生成树(最小支撑树)的值。
思路：
过程：
本题调试问题出在如下几处：
1.用%c会读入回车符(用getchar()有的平台又会出问题)，所以以后读字符都直接用%s,然后在取字符串第一个字符即可。
char c[4];
scanf("%s",c);
printf("%c",c[0]);
2.边排序后遍历所有边，我犯了个错(以为只要所有点都出现过，那后面的边就不用遍历了)，忘记了即使所有点都出现过，
也可能分散在多个连通分量内，所以最小支撑树不一定已生成。最保险的方式还是把所有边，一个个全遍历完。
3.本题测试用例不太符合题目要求，既有A 1 A 24这种自环边，也有D 2 A 45 C 5这种(ASCII大的后面跟小的)，重复的A 2 B 44 B 100.
代码：
#include <iostream>
#include <stdio.h>
#include <cstring>
#include <algorithm>
using namespace std;
//边结构体
struct Edge{
char Node1; //边的两点
char Node2;
int value; //边值
};
//相关变量和函数
Edge edge[77]; //边数组
int inputNum; //输入边的个数
int joinMark[26]; //A-Z是否参与,0:没参加;1:参加
char storeTree[26]; //并查集，存树
char find(char c){ //查找结点c的根
char cc=c;
while(storeTree[cc-65]!=cc){
cc=storeTree[cc-65];
}
return cc;
}
bool cmp(Edge e1,Edge e2){ //边值大小比较函数
if(e1.value<=e2.value)
return true;
return false;
}
//主函数
int main(){
int n,n2,i,sum; //n:参与点的个数,n2:n的备份,sum:支撑树的边和
char node1[5],node2[5]; //边的两点
int k,cost; //k:每行输入k个边;cost:边的值
while(scanf("%d",&n)!=EOF && n){ //输入n(n=0时退出)
//memset(edge,0,77*sizeof(Edge)); //初始化变量值
inputNum=0;
memset(joinMark,0,26*sizeof(int));
for(i=0;i<26;i++)
storeTree[i]=char(i+65);
sum=0;
n2=n; //边的输入
while(--n2){ //n-1行输入
scanf("%s %d",node1,&k);
while(k--){ //每行k个边
scanf("%s %d",node2,&cost);
edge[inputNum].Node1=node1[0];
edge[inputNum].Node2=node2[0];
edge[inputNum].value=http://www.mamicode.com/cost;"%d\n",sum); //输出结果
}
return 0;
}
北大 2012 Jungle Roads
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。