九度|最小生成树并查集|kruskal算法|最小生成树

最小生成树：

在一个无向连通图中，如果存在一个连通子图包含原图中所有结点和部分边，且这个子图不存在回路，则这个子图是原图的一棵生成树。在带权图中，所有生成树中边权最小的那棵或几棵称为生成树。

Kruskal算法求最小生成树：

1，首先所有结点都属于孤立的集合；
2，按照边权从小到大的顺序遍历所有的边，如果遍历到的边连接的两个结点在不同的集合中，则合并这两个集合；
3，当所有的边遍历完成时，如果只存在一个连通分量，则该连通分量就是我们要求的最小生成树；如果不止存在一个连通分量，则说明原图不连通，不存在最小生成树。
可以看出Kruskal算法求解最小生成树涉及很多的集合操作，所以可以将并查集运用其中。

九度1017：还是畅通工程题目地址：http://ac.jobdu.com/problem.php?pid=1017
题目描述：
某省调查乡村交通状况，得到的统计表中列出了任意两村庄间的距离。省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通（但不一定有直接的公路相连，只要能间接通过公路可达即可），并要求铺设的公路总长度为最小。请计算最小的公路总长度。

输入：: 测试输入包含若干测试用例。每个测试用例的第1行给出村庄数目N ( < 100 )；随后的N(N-1)/2行对应村庄间的距离，每行给出一对正整数，分别是两个村庄的编号，以及此两村庄间的距离。为简单起见，村庄从1到N编号。
当N为0时，输入结束，该用例不被处理。

输出：: 对每个测试用例，在1行里输出最小的公路总长度。

样例输入：: 3 1 2 1 1 3 2 2 3 4 4 1 2 1 1 3 4 1 4 1 2 3 3 2 4 2 3 4 5 0

样例输出：

3 5

【九度|最小生成树】 解题思路：根据题意（使全省任何两个村庄间都可以实现公路交通，计算最小的公路总长度）可以看出是要求最小生成树。

#include #include #include using namespace std; #define N 101 int root[N]; struct Edge{ int v1; //顶点1 int v2; //顶点2 int cost; //边的权值 //重载操作符<，方便按边的权值进行排序 bool operator < (const Edge &A) const{ return cost < A.cost; } }; int findroot(int x){ if(root[x] == -1) return x; else{ int tmp = findroot(root[x]); root[x] = tmp; return tmp; } } int main(){ int n; while(cin >> n){ if(n == 0) break; for(int i = 1; i <= n; i++) root[i] = -1; int e = n * (n - 1) / 2; vector edge; for(int i = 0; i < e; i++){ Edge e; cin >> e.v1 >> e.v2 >> e.cost; edge.push_back(e); } //按边的权值进行排序 sort(edge.begin(),edge.end()); int ans = 0; for(int i = 0; i < e; i++){ int a = findroot(edge[i].v1); int b = findroot(edge[i].v2); if(a != b){ root[a] = b; ans += edge[i].cost; } } cout << ans << endl; }return 0; } /************************************************************** Problem: 1017 User: cherish Language: C++ Result: Accepted Time:30 ms Memory:1712 kb ****************************************************************/

九度1144：Freckles 题目地址：http://ac.jobdu.com/problem.php?pid=1144
题目描述：: In an episode of the Dick Van Dyke show, little Richie connects the freckles on his Dad's back to form a picture of the Liberty Bell. Alas, one of the freckles turns out to be a scar, so his Ripley's engagement falls through.
Consider Dick's back to be a plane with freckles at various (x,y) locations. Your job is to tell Richie how to connect the dots so as to minimize the amount of ink used. Richie connects the dots by drawing straight lines between pairs, possibly lifting the pen between lines. When Richie is done there must be a sequence of connected lines from any freckle to any other freckle.

输入：: The first line contains 0 < n <= 100, the number of freckles on Dick's back. For each freckle, a line follows; each following line contains two real numbers indicating the (x,y) coordinates of the freckle.

输出：: Your program prints a single real number to two decimal places: the minimum total length of ink lines that can connect all the freckles.

样例输入：: 3 1.0 1.0 2.0 2.0 2.0 4.0

样例输出：: 3.41

解题思路：题目给出的是每个雀斑的坐标，要求连接这些雀斑所需要的最少的墨水...（真无聊==）
中心思想也是以各个雀斑为顶点求最小生成树。但是给出的坐标，所以还需要进行一下处理，计算每两个顶点之间的距离，回归到最小生成树正常情形。

#include #include #include #include #include using namespace std; #define N 101 int root[N]; //存储节点的父节点，用来供并查集使用 struct Vertex{ double x; double y; }; struct Edge{ int v1; int v2; double cost; bool operator <(const Edge &A) const{ return cost < A.cost; } }; //查找节点x所在树的根结点 int findroot(int x){ if(root[x] == -1) return x; else{ int tmp = findroot(root[x]); root[x] = tmp; //路径压缩 return tmp; } }int main(){ int n; while(cin >> n){ if(n == 0) break; for(int i = 0; i < n; i++) root[i] = -1; vector vertex_vec; //存储节点 vector edge_vec; //存储边for(int i = 0; i < n; i++){ Vertex v; cin >> v.x >> v.y; vertex_vec.push_back(v); }//每两个不同的节点组成一条边 for(int i = 0; i < n; i++){ for(int j = i + 1; j < n; j++){ Edge e; e.v1 = i; e.v2 = j; double a = vertex_vec[i].x - vertex_vec[j].x; double b = vertex_vec[i].y - vertex_vec[j].y; e.cost = sqrt(a * a + b * b); edge_vec.push_back(e); } }//按边的权值进行排序 sort(edge_vec.begin(),edge_vec.end()); double ans = 0; for(int i = 0; i < edge_vec.size(); i++){//查找该边的两个顶点的集合信息 int a = findroot(edge_vec[i].v1); int b = findroot(edge_vec[i].v2); //如果两个顶点在不同的集合 if(a != b){ root[a] = b; //合并两个集合 ans += edge_vec[i].cost; //把该边的权值加入 } }cout << fixed << setprecision(2) << ans << endl; }return 0; } /************************************************************** Problem: 1144 User: cherish Language: C++ Result: Accepted Time:10 ms Memory:1780 kb ****************************************************************/

九度1154：Jungle Roads 题目地址：http://ac.jobdu.com/problem.php?pid=1154
题目描述：: 文章图片

The Head Elder of the tropical island of Lagrishan has a problem. A burst of foreign aid money was spent on extra roads between villages some years ago. But the jungle overtakes roads relentlessly, so the large road network is too expensive to maintain. The Council of Elders must choose to stop maintaining some roads. The map above on the left shows all the roads in use now and the cost in aacms per month to maintain them. Of course there needs to be some way to get between all the villages on maintained roads, even if the route is not as short as before. The Chief Elder would like to tell the Council of Elders what would be the smallest amount they could spend in aacms per month to maintain roads that would connect all the villages. The villages are labeled A through I in the maps above. The map on the right shows the roads that could be maintained most cheaply, for 216 aacms per month. Your task is to write a program that will solve such problems.

输入：: The input consists of one to 100 data sets, followed by a final line containing only 0. Each data set starts with a line containing only a number n, which is the number of villages, 1 < n < 27, and the villages are labeled with the first n letters of the alphabet, capitalized. Each data set is completed with n-1 lines that start with village labels in alphabetical order. There is no line for the last village. Each line for a village starts with the village label followed by a number, k, of roads from this village to villages with labels later in the alphabet. If k is greater than 0, the line continues with data for each of the k roads. The data for each road is the village label for the other end of the road followed by the monthly maintenance cost in aacms for the road. Maintenance costs will be positive integers less than 100. All data fields in the row are separated by single blanks. The road network will always allow travel between all the villages. The network will never have more than 75 roads. No village will have more than 15 roads going to other villages (before or after in the alphabet). In the sample input below, the first data set goes with the map above.

输出：: The output is one integer per line for each data set: the minimum cost in aacms per month to maintain a road system that connect all the villages. Caution: A brute force solution that examines every possible set of roads will not finish within the one minute time limit.

样例输入：: 9 A 2 B 12 I 25 B 3 C 10 H 40 I 8 C 2 D 18 G 55 D 1 E 44 E 2 F 60 G 38 F 0 G 1 H 35 H 1 I 35 3 A 2 B 10 C 40 B 1 C 20 0

样例输出：: 216 30

解题思路：也是基本的求最小生成树的题目。只需注意一下输入数据的形式和处理。

#include #include #include using namespace std; int root[30]; struct Road{ int village1; int village2; int distance; //重载<操作符，便于根据distance对road进行排序 bool operator < (const Road &R) const{ return distance < R.distance; } }; //查找x节点所在的树的根节点 int findroot(int x){ if(root[x] == -1) return x; else{ int tmp = findroot(root[x]); root[x] = tmp; return tmp; } } int main(){ int n; while(cin >> n){ if(n == 0) break; vector road_vec; for(int i = 1; i <= n; i++) root[i] = -1; for(int i = 0; i < n - 1; i++){ char c; int num; cin >> c >> num; if(num >> 0){ Road r; for(int j = 0; j < num; j++){ char tmpc; int dis; cin >> tmpc >> dis; //A表示1号village，B表示2号... r.village1 = c - 'A' + 1; r.village2 = tmpc - 'A' + 1; r.distance = dis; road_vec.push_back(r); } } }sort(road_vec.begin(),road_vec.end()); int ans = 0; for(int i = 0; i < road_vec.size(); i++){ int a = findroot(road_vec[i].village1); int b = findroot(road_vec[i].village2); if(a != b){ root[a] = b; ans += road_vec[i].distance; } }cout << ans << endl; }return 0; } /************************************************************** Problem: 1154 User: cherish Language: C++ Result: Accepted Time:0 ms Memory:1520 kb ****************************************************************/

九度1024：畅通工程题目地址：http://ac.jobdu.com/problem.php?pid=1024
题目描述：: 省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通（但不一定有直接的公路相连，只要能间接通过公路可达即可）。经过调查评估，得到的统计表中列出了有可能建设公路的若干条道路的成本。现请你编写程序，计算出全省畅通需要的最低成本。

输入：: 测试输入包含若干测试用例。每个测试用例的第1行给出评估的道路条数 N、村庄数目M (N, M < =100 )；随后的 N 行对应村庄间道路的成本，每行给出一对正整数，分别是两个村庄的编号，以及此两村庄间道路的成本（也是正整数）。为简单起见，村庄从1到M编号。当N为0时，全部输入结束，相应的结果不要输出。

输出：: 对每个测试用例，在1行里输出全省畅通需要的最低成本。若统计数据不足以保证畅通，则输出“?”。

样例输入：: 3 3 1 2 1 1 3 2 2 3 4 1 3 2 3 2 0 100

样例输出：: 3 ?

解题思路：也是基本的求解最小生成树的问题。但是要注意的是该题与上面几题不同的是，这题中不一定存在最小生成树，该题中全省的所有村庄不一定全部连通。

#include #include #include using namespace std; #define N 101 int root[N]; struct Road{ int v1; //村庄1 int v2; //村庄2 int cost; //连接村庄1和村庄2的cost bool operator < (const Road &R) const{ return cost < R.cost; } }; //查找x节点所在的树的根节点 int findroot(int x){ if(root[x] == -1) return x; else{ int tmp = findroot(root[x]); root[x] = tmp; //路径压缩 return tmp; } } int main(){ int n,m; while(cin >> n){ if(n == 0) break; cin >> m; vector road_vec; for(int i = 1; i <= m; i++) root[i] = -1; for(int i = 0; i < n; i++){ Road r; cin >> r.v1 >> r.v2 >> r.cost; road_vec.push_back(r); }sort(road_vec.begin(),road_vec.end()); int ans = 0; for(int i = 0; i < road_vec.size(); i++){ int a = findroot(road_vec[i].v1); int b = findroot(road_vec[i].v2); //如果道路road_vec[i]连接的两个村庄不在同一个集合则进行合并 if(a != b){ root[a] = b; //合并 ans += road_vec[i].cost; //把该道路的cost加入 } }//判断整个省是否全部连通，如果所有村庄都在同一个集合，则所有村庄全部连通 //cnt用来记录连通分量的个数 int cnt = 0; for(int i = 1; i <= m; i++) if(root[i] == -1) cnt++; if(cnt > 1) cout << "?" << endl; else cout << ans << endl; }return 0; } /************************************************************** Problem: 1024 User: cherish Language: C++ Result: Accepted Time:10 ms Memory:1520 kb ****************************************************************/