题目链接 :http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=1048
解题报告:在zoj上wa了多次还是过不了,感觉很郁闷,就去poj上提交,结果poj可以过。
代码其实很快就敲出来了,只是一直wa改了很久也没有发现错误,刚开始我还以为是已经完全联通的城市需要输出一个空行呢,结果只是两组数据之间夹一个空行,zoj上顺利通过,希望wa的可以借鉴一下。
代码:
#include<cstdio> #include<cstring> #include<cmath> #define maxn 800 #define INF 0x7fffffff using namespace std; struct node { int x, y; }vex[maxn]; int edge[maxn][maxn]; int nearvex[maxn]; int lowcost[maxn]; int n, m; void Prim( int u0 ) { int i, j, flag = 0; for( i = 1; i <= n; i++ ) { lowcost[i] = edge[u0][i]; nearvex[i] = u0; } nearvex[u0] = -1; for( i = 1; i < n; i++ ) { int min = INF; int v = -1; for( j = 1; j <= n; j++ ) { if(nearvex[j] != -1 && lowcost[j] < min ) { min = lowcost[j] ; v = j; } } if( v != -1) { if(min == 0) { nearvex[v] = -1; } else { printf("%d %d\n",nearvex[v],v); flag = 1; nearvex[v] = -1; } } for( j = 1; j <= n; j++ ) { if( nearvex[j] != -1 && edge[v][j] < lowcost[j] ) { lowcost[j] = edge[v][j]; nearvex[j] = v; } } } // if(!flag) printf("\n"); // else printf("\n\n"); } int main( ) { int T, i, j, u, v; scanf("%d", &T); while( T-- ) { memset(edge, 0, sizeof(edge)); memset(nearvex, 0, sizeof(nearvex)); memset(lowcost, 0, sizeof(lowcost)); scanf( "%d", &n ); for( i = 1; i <= n; i++ ) scanf("%d %d", &vex[i].x, &vex[i].y); for( i = 1; i <= n; i++ ) { for( j = 1; j <= n; j++ ) { if(i == j ) edge[i][j] = INF; else if(i < j) edge[i][j] = edge[j][i] = (vex[i].x-vex[j].x)*(vex[i].x-vex[j].x)+(vex[i].y-vex[j].y)*(vex[i].y-vex[j].y); } } scanf("%d",&m); for( j = 0; j < m; j++ ) { scanf("%d%d", &u, &v); edge[u][v] = edge[v][u] = 0; } Prim( 1 ); if(T) printf("\n"); } return 0; }
相关推荐
Swordfish 用最小生成树prim实现的程序代码 已经AC了
学习ACM程序设计的朋友一定要看,这是训练必备的POJ ZOJ题目分类及解题思路
利用vjudge源码改造爬虫抓取vjudge全局共享答案资源。 ACMer,请用于参考思路,对拍代码,不要直接提交。
自动探测POJ、HDU、SOJ、ZOJ水题,对于有志于刷遍各种水题的ACMer来说非常有用
Interview,ZOJ,POJ 等平台。 欢迎Coders对代码加以指正和提议! 常见问题总结 两整数求平均值 average = min + (max - min) / 2 防止两整数的和越界 整数乘积对比 1.0 * m * m == num 类似乘积对比, 需转为double...
ZOJ解题报告ZOJ解题报告ZOJ解题报告ZOJ解题报告
zoj题目简单归类zoj题目简单归类zoj题目简单归类
acm中zoj1002的可运行C++程序
包含了zoj700多道题目的源代码,在做题时可以参考
ZJU/zoj 题库上的部分题源码 本人博客: hi.baidu.com/xiaoxianxi_acm
acm 模板 算法 浙大 zoj zju acm初学者必备 代码
Problem Arrangement zoj 3777
ZOJ题目答案源码
一个非常非常非常非常实用的zoj结题代码
ZOJ题解集合-截至2835。共1244个文件,C/C++,有重复
每一个都有代码和注释,分析,很好的算法练习 实验一:递归与分治 1. 二分查找 2. 合并排序 3. 快速排序 实验二:回溯 1. 0-1背包问题 2. 装载问题 3. 堡垒问题(ZOJ1002) 4. *翻硬币问题 5. 8皇后问题 6. 素数环...
这是一份ZOJ的ACM题解,包含大多数题目的AC程序,是学习算法的好东西~
zoj 1003 c语言的,要写这么多描述吗。。
ZOJ1805代码
本代码是zoj上AC的1951的代码,把双重循环简化为O(n),不过素数判断的改进还不够