链接：/problem/POJ-1251
题意：
热带岛屿Lagrishan的头长老有问题。几年前，在村庄之间的额外道路上花了一大笔外援资金。但丛林无情地超越了道路，因此大型公路网络的维护成本太高。长老理事会必须选择停止维持一些道路。左上方的地图显示了现在使用的所有道路以及维护它们的每月aacms的成本。当然，即使路线不像以前那么短，也需要在维护道路上的所有村庄之间进行某种方式。首席长老想告诉长老会，他们每月可以花费最少的金额来维持连接所有村庄的道路。在上面的地图中，村庄标有A到I.右边的地图显示了最便宜的道路，每月216个aacms。你的任务是编写一个可以解决这些问题的程序。
思路：
kruskal模板题
代码：
#include <iostream>#include <memory.h>#include <string>#include <istream>#include <sstream>#include <vector>#include <stack>#include <algorithm>#include <map>#include <queue>#include <math.h>using namespace std;typedef long long LL;const int MAXM = 1000;const int MAXN = 30;struct Path{int _l;int _r;int _value;bool operator < (const Path & that)const {return this->_value < that._value;}}path[MAXM];int Father[MAXN];int Get_F(int x){return Father[x] = (Father[x] == x) ? x : Get_F(Father[x]);}int main(){int t,n,m;while (~scanf("%d",&n)&&n){for (int i = 1;i<=n;i++)Father[i] = i;char s[10];char node[10];int v;n--;int pos = 0;while (n--){scanf("%s%d",s,&m);while (m--){scanf("%s%d",node,&v);path[++pos]._l = s[0] - 'A' + 1;path[pos]._r = node[0] - 'A' + 1;path[pos]._value = v;}}sort(path+1,path+1+pos);int sum = 0;for (int i = 1;i<=pos;i++){int tl = Get_F(path[i]._l);int tr = Get_F(path[i]._r);if (tl != tr){Father[tl] = tr;sum += path[i]._value;}}printf("%d\n",sum);}return 0;}
如果觉得《POJ-1251-Jungle Roads》对你有帮助，请点赞、收藏，并留下你的观点哦！
