poj-1287 不是题目水,而是数据弱
这个题目很简单,就是最简单的最小生成树,并且用克鲁斯卡尔算法很容易。
但是,题目中说的边可能是无限的(The number of possible routes is unlimited),如果边有很多,该如何办呢?
当然,这里直接开10000条以上就行了,因为测试用例有限,加入10^10条呢?
这里说了最多50个点,那么最多也就1225条边,再多就是重复的,实际上我们只需要开这么大的空间就行,然后读入所有的边,将重复的保存最小值就可以了。
不过这里没必要,因为,边数比较少。。。。
直接代码,要想懂得此题目,首先要看看数据结构-并查集,不过本题目用普利姆算法可能更快点,因为点少,o(n^2).
#include <cstdio>#include <iostream>#include <algorithm>using namespace std;#definenMaxEdgeNum 15000//最大边数#define nMaxPointNum 100//最多点数int father[nMaxPointNum];//并查集模拟树的数组int rank[nMaxPointNum];//typedef struct EDGE{int u, v, w;}Edge;Edge edge[nMaxEdgeNum];int p, r, sum;//比较函数bool cmp(Edge a, Edge b){return a.w < b.w;}//下面依次是并查集的三个函数//初始化void Init(int n){for (int i = 1; i <= n; ++ i){father[i] = i;rank[i] = 0;}}//查找int Find(int x){if (x != father[x]){father[x] = Find(father[x]);}return father[x];}//合并void Union(int x, int y){int xx = Find(x);int yy = Find(y);if (rank[xx] > rank[yy]){father[yy] = xx;}else{father[xx] = yy;if (rank[xx] == rank[yy]){rank[yy] ++;}}}//克鲁斯卡尔算法实现void Kruskal(){sum = 0;Init(p);sort(edge + 1, edge + r + 1, cmp);for (int i = 1; i <= r; ++ i){if (Find(edge[i].u) != Find(edge[i].v)){sum += edge[i].w;Union(edge[i].u, edge[i].v);}}printf("%d\n",sum);}int main(){while (scanf("%d", &p) && p){scanf("%d", &r);for (int i = 1; i <= r; ++ i){scanf("%d %d %d",&edge[i].u, &edge[i].v, &edge[i].w);}Kruskal();}return 0;}