题目链接 :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题目分类及解题思路
图论则涉及到最短路径算法(Dijkstra算法、Floyd-Warshall算法)、最小生成树(Prim算法、Kruskal算法)等。 此外,源码中可能会包含一些高级主题,如回溯法(用于解决组合优化问题,如八皇后问题、N皇后问题等)、...
题目编号1002,通常表示该题是ZOJ平台上的一个问题,可能涉及算法、数据结构或特定编程技巧的运用。 【描述】"ACM中ZOJ1002的可运行C++程序" 提示我们,这个压缩包包含了一个用C++语言编写的程序,该程序是为了解决...
利用vjudge源码改造爬虫抓取vjudge全局共享答案资源。 ACMer,请用于参考思路,对拍代码,不要直接提交。
- POJ 1789: Prim算法应用 - POJ 2485: Kruskal算法实例 - POJ 1258: 最小生成树问题 - POJ 3026: 最小生成树变种 - **网络流**:Ford-Fulkerson算法、Edmonds-Karp算法等。 - **示例题目**: - POJ 1094: ...
【标题】"zoj 源码700题"是指一个包含700多道ZOJ(在线判题系统Zhejiang Online Judge)编程竞赛题目的源代码集合。这个资源对于学习算法、提高编程技能以及准备编程竞赛的学员来说极具价值。 【描述】"包含了zoj...
【标题】"ZJU/zoj 题库上的部分题源码"涉及的知识点主要集中在ACM(国际大学生程序设计竞赛)编程领域,尤其是浙江大学(ZJU)ZOJ(Zhejiang University Online Judge)题库中的题目解决方案。ZOJ是一个在线编程评测...
ZOJ是一个在线编程竞赛平台,它为参赛者提供了一系列算法题目进行练习,以提升编程和算法解决能力。这个压缩包尤其对那些希望在ACM竞赛中提升自己的选手来说,是非常有价值的资源。 【Jugs A】可能是指ZOJ中的一个...
5. **图论**:最小生成树(Prim 或 Kruskal 算法)、最短路径(Floyd-Warshall、Bellman-Ford、Dijkstra 等)、拓扑排序、网络流等问题,这些在解决实际问题如交通网络、电路设计等领域有广泛应用。 6. **字符串...
标题中的“POJ、HDU、ZOJ、SOJ水题过滤器”指的是一个工具,它主要用于帮助在ACM(国际大学生程序设计竞赛)训练中筛选出这些在线判题系统中的简单题目,即所谓的“水题”。这些在线判题平台是编程爱好者和参赛者们...
浙江大学ZOJ题目分类旨在为编程学习者提供一个系统化的训练平台,帮助他们在算法和编程技能上实现质的飞跃。ZOJ平台提供的分类题目包括但不限于基础算法、数据结构、动态规划以及模拟问题等,这些分类覆盖了计算机...
1. **算法选择**:在解决ZOJ 4041时,选择正确的算法至关重要。可能是动态规划、贪心策略、回溯法或者图论中的某一种。每种算法都有其特定的应用场景,选择最能适应问题特性的算法是优化解决方案的关键。 2. **时间...
ZOJ,全称“浙江大学程序在线评测系统”(Zhejiang University Online Judge),是一个提供信息学(算法竞赛)题库及程序评测的网站。以下是关于ZOJ的详细介绍: 一、基本信息 名称:浙江大学程序在线评测系统(ZOJ)...
该资源主要涵盖了 zoj 题库中的各种编程题目,涵盖了基本算法、数据结构、数学运算等多个方面的知识点。下面是对该资源中出现的知识点的详细解释: 1. 第一次 ACM 总结(7th ACM) 该题目主要考察了基本的算法设计...
本资料包聚焦于三大OJ平台——PKU(北京大学)、HDOJ(杭州电子科技大学)和ZOJ(浙江大学),它们都提供了丰富的题目资源,尤其是针对不同算法的分类,对于学习和准备ACM(国际大学生程序设计竞赛)或者其他算法...
标题中的"ZOJ.gz_ ZOJ_ZOJ 1016_max flow_zoj 1045_zoj.rar" 提到了两个ZOJ(Zhejiang Online Judge)的题目,分别是1016和1045,这两个数字通常代表在线编程竞赛中的题目编号。这些题目通常涉及到算法和数据结构的...
【标题】"浙大ZOJ月赛解题报告及代码"揭示了这是一份与浙江大学ZOJ在线评测系统相关的竞赛编程资源,特别是针对月度竞赛的解题总结和实现代码。ZOJ,全称为Zhejiang University Online Judge,是浙江大学维护的一个...
ZOJ,全称为“Zhejiang Online Judge”,是浙江大学主办的一个在线编程竞赛平台,提供了丰富的算法题目供参赛者练习和挑战。本解题指南可能包含了对该题目的深入解析、思路引导、算法设计以及优化建议,旨在帮助参赛...
ZOJ,全称为Zhejiang Online Judge,是一个知名的在线编程竞赛平台,主要服务于浙江大学和国内其他高校的学生,提供丰富的算法题目供参赛者练习和比赛。这个压缩包文件名为"ZOJ 700多题源代码",意味着它包含了解决...