zoj - 1406 - Jungle Roads
题意:有n个村庄,村庄间有一些路,但有一些路可以不要也可连通所有村庄,为节约费用,deal with一些不必要的路,求最少维护总费用。
——>>用Kruscal算法生成一棵最小生成树,输出即可。
[cpp]
#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 && !q
补充:软件开发 , C++ ,