POJ1251 Jungle Roads【最小生成树】

题意:

首先给你一个图,需要你求出最小生成树,首先输入n个节点,用大写字母表示各节点,接着说有几个点和它相连,然后给出节点与节点之间的权值。
拿第二个样例举例:比如有3个节点,然后接下来有3-1行表示了边的情况,拿第一行来说:
A 2 B 10 C 40
表示A有2个邻点,B和C,AB权值是10,AC权值是40。

思路:

直接套prime算法模板和kuskal算法模板,然后处理下数据就可以了。

代码:

prime:

#include <iostream>
#include <cstdio>
#include <string.h>
using namespace std;
const int maxn=;
const int inf=0x3f3f3f3f;
int road[maxn][maxn],dis[maxn];
bool vis[maxn];
int n; void prim()
{
int minn, v;
for(int i = ; i < n; i++)
{
dis[i] = road[][i];
vis[i] = false;
}
for(int i = ; i <= n; i++)//包括第一个点在内,一共要纳入n个点
{
minn = inf;
for(int j = ; j < n; j++)//每次找出未纳入顶点集与已知顶点集构成的权值最小的一条边
{
if(!vis[j] && minn > dis[j])
{
v = j;
minn = dis[j];
}
}
vis[v] = true;//把该顶点纳入已知集合
for(int j = ; j < n; j++)//更新与未纳入集合中的顶点的边的最小权值
{
if(!vis[j] && dis[j] > road[v][j])
dis[j] = road[v][j];
}
}
for(int i = ; i < n; i++)
dis[] += dis[i];
cout << dis[] << endl;
} int main()
{
int m,w;
char a[],b[];
while(cin>>n,n)
{
memset(road,,sizeof(road));
for(int i=;i<n;i++)
road[i][i]=;
for(int i=;i<n;i++)
{
scanf("%s%d",a,&m);
for(int j=;j<m;j++)
{
scanf("%s%d",b,&w);
road[a[]-'A'][b[]-'A']=road[b[]-'A'][a[]-'A']=w;
}
}
prim();
}
return ;
}

kruskal:

#include<iostream>
#include<algorithm>
using namespace std;
int p[]; struct node
{
int villagea;
int villageb;
int distance;
}roads[]; bool cmp(node a, node b)
{
return a.distance < b.distance;
} int kruskal(int x)
{
return p[x] == x ? x : p[x] = kruskal(p[x]);
} int main()
{
int n, k, distance, number, ans;
char start_village, end_village;
while(cin >> n, n)
{
ans = k = ;
for(int i = ; i < ; i++)
p[i] = i;
for(int i = ; i < n- ; i++)
{
cin >> start_village >> number;
for(int j = ; j < number; j++, k++)
{
cin >> end_village >> distance;
roads[k].villagea = start_village - 'A';
roads[k].villageb = end_village - 'A';
roads[k].distance = distance;
}
}
sort(roads, roads + k, cmp);
for(int i = ; i < k; i++)
{
int x = kruskal(roads[i].villagea);
int y = kruskal(roads[i].villageb);
if(x != y)
{
ans = ans + roads[i].distance;
p[y] = x;
}
}
cout << ans << endl;
}
return ;
}
上一篇:机器学习Python实现 SVD 分解


下一篇:【机器学习】推荐系统、SVD分解降维