从A到F找到最短路即可,由于我不会用prim算法
只能用ku...算法,幸好这道题没有让输出路路径,
所以用ku...算法也行
我通常都是这样写的1.把边存起来2.快排3.并查集
呵呵,过了,还行吧,对了输入注意用scanf
中的%d前加一个空格
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
typedef struct Tedge
{
int from,to;
int dist;
}edge;
edge dis[100];
int N;
int fa[30];
int find(int x)
{
if(x == fa[x])
return x;
fa[x] = find(fa[x]);
return(fa[x]);
}
int cmp(const void *a,const void *b)
{
return (*(edge *)a).dist - (*(edge *)b).dist;
}
int main()
{
int n,sub,m,d,i,count,sum;
char ch;
while(scanf("%d",&n)==1,n)
{
N = 0;
sub = n;
sub -= 1;
while(sub--)
{
scanf(" %c",&ch);
dis[N].from = ch - 'A' + 1;
scanf("%d",&m);
for(i=1;i<m;i++)
dis[N+i].from = dis[N].from;
while(m--)
{
scanf(" %c",&ch);
scanf("%d",&d);
dis[N].to = ch - 'A' + 1;
dis[N].dist = d;
N++;
}
} //输入完成
qsort(dis,N,sizeof(edge),cmp);
for(i=1;i<=n;i++)
fa[i] = i;
count =0;
sum = 0;
for(i=0;i<N;i++)
{
if(find(dis[i].from) != find(dis[i].to))
{
fa[find(dis[i].from)] = find(dis[i].to);
sum += dis[i].dist;
count++;
if(count == (n-1))break;
}
}
printf("%d\n",sum);
}
return 0;
}
分享到:
相关推荐
ZOJ解题报告ZOJ解题报告ZOJ解题报告ZOJ解题报告
zoj题目简单归类zoj题目简单归类zoj题目简单归类
acm中zoj1002的可运行C++程序
包含了zoj700多道题目的源代码,在做题时可以参考
Problem Arrangement zoj 3777
ZOJ题目答案源码
学习ACM程序设计的朋友一定要看,这是训练必备的POJ ZOJ题目分类及解题思路
一个非常非常非常非常实用的zoj结题代码
zoj 1003 c语言的,要写这么多描述吗。。
浙大ZOJ题目分类,可以让你更方便快速锁定那你想要联系的题目,是自己快速提高·
本代码是zoj上AC的1951的代码,把双重循环简化为O(n),不过素数判断的改进还不够
ZOJ1805代码
zoj1027解题指南和代码,还不错,是学校培训给的。
ZOJ题解集合-截至2835。共1244个文件,C/C++,有重复
zoj 题库 详细解答 解题代码 acm
zoj4041正确题解源代码,以及运行程序
zoj吐血制作,希望大家喜欢
大学ACM竞赛,ZOJ 1733 运用递归(优化)的方法。ac的代码。
能AC 通过的c++代码,包括zoj1002,1091,1789
zoj3464 Rugby Football测试数据