本文主要是介绍zoj - 1406 - Jungle Roads，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：有n个村庄，村庄间有一些路，但有一些路可以不要也可连通所有村庄，为节约费用，deal with一些不必要的路，求最少维护总费用。
题目链接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=406
——>>用Kruskal算法生成一棵最小生成树，输出即可。
#include <iostream>
#include <queue>
#include <string.h>using namespace std;const int maxn = 30; //1<n<27，开30够了struct edge //定义边数据类型
{int v1; //边的端点之一int v2; //边的端点之一int cost; //一个月维护这条路的费用
};bool operator < (edge e1, edge e2) //定义优先队列排序方式
{return (e1.cost > e2.cost);
}int fa[maxn], height[maxn]; //fa[x]为x的父亲，height[i]以i为根的树的高度（并查集）
int find(int x) //找x的根（并查集）
{while(fa[x] != x){x = fa[x];}return x;
}bool judge(int x, int y) //判断加入边x——y后是否会开成环，会的返回0，不会的话返回1
{int new_x = find(x);int new_y = find(y);if(new_x == new_y) return 0; //会形成环else //不会形成环{if(height[new_x] > height[new_y]) fa[new_y] = new_x;else if(height[new_x] == height[new_y]){fa[new_y] = new_x;height[new_x]++;}else fa[new_x] = new_y;return 1;}
}bool G[maxn][maxn]; //用邻接矩阵来存储图
bool vis[maxn], viss[maxn]; //vis、viss均用来判断该村庄是否走过
int n; //n个村庄void dfs(int i) //深度优先遍历修改一个连通块
{vis[i] = 1;int j;for(j = 1; j <= n; j++)if(G[i][j] == 1 && vis[j] == 0)dfs(j);return;
}bool is_ok() //判断村庄是否已连通
{memset(viss, 0, sizeof(viss));int count = 0, ok = 1, i;for(i = 1; i <= n; i++){if(viss[i] == 0){dfs(i);count++;if(count >= 2){ok = 0;break;}}}if(ok) return 1;else return 0;
}int main()
{int i, j;while(cin>>n){if(n == 0) return 0;char c1, c2;int num1, num2;for(i = 1; i <= n; i++){fa[i] = i;height[i] = 1;}priority_queue<edge> qu; //用优先队列取最小费用的路径edge newnode;memset(G, 0, sizeof(G));for(i = 1; i <= n-1; i++){cin>>c1>>num1;for(j = 1; j <= num1; j++){cin>>c2>>num2;G[(int)(c1-'A')+1][(int)(c2-'A')+1] = 1; //把A,B,C...变成1,2,3...G[(int)(c2-'A')+1][(int)(c1-'A')+1] = 1;newnode.v1 = (int)(c1-'A')+1;newnode.v2 = (int)(c2-'A')+1;newnode.cost = num2;qu.push(newnode); //入列}}int sum = 0; //费用总数int OK = 0; //整个island是否连通的标志memset(vis, 0, sizeof(vis));while(!OK && !qu.empty()){if(judge(qu.top().v1, qu.top().v2)) //用并查集实现判断加入那条边是否会形成环，不会的时候{OK = 0;vis[qu.top().v1] = 1; //将这两个村庄标记为已走vis[qu.top().v2] = 1;sum += qu.top().cost; //累加总费用if(is_ok()) OK = 1; //加入此边后判断所有村庄是否已连通}qu.pop();}cout<<sum<<endl;}return 0;
}
这篇关于zoj - 1406 - Jungle Roads的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
