Jungle Roads 最小生成树
程序员文章站
2022-06-16 08:57:48
...
Jungle Roads
原题链接https://vjudge.net/contest/352170#problem/A
也算是最小生成树的板子,对于题目给的数据要进行读取,将ABCDE转化为我们常用的12345,题目中已经将所有的路都给出来了,我们只需要读取然后使用最小生成树计算即可。
Prim:
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <queue>
#include <stack>
using namespace std;
const int INF = 0x3f3f3f3f;//标记最大值
long long map[105][105];//记录所有情况
long long ans;
long long n;
bool vis[30005];//是否使用
long long dis[300005];//距离
void prim()
{
ans = 0;
long long i, j;
for (i = 1; i <= n; i++)
{
dis[i] = map[1][i];//读取1地点与其他地点的距离
vis[i] = false;//所有情况初始化为未使用
}
vis[1] = true;//从1开始使用,所以1被用了
for (i = 1; i < n;i++)
{
long long minn = INF;
long long p = 1;
for (j = 1; j <= n;j++)
{
if(!vis[j]&&dis[j]<minn)//遍历寻找最小距离
{
minn = dis[j];
p = j;
}
}
if(minn==INF)//如果没有最小值,说明不能连接
{
ans = -1;
return;
}
ans += minn;//记录答案
vis[p] = true;//标记
for (j = 1; j <= n;j++)//对于我们找到的与上一个点最小距离的点,寻找记录他的距离,下次连接他
{
if(!vis[j]&&map[p][j]<dis[j])
dis[j] = map[p][j];
}
}
return;
}
int main()
{
long long i, j, a, b;
while (~scanf("%lld", &n))
{
if (n == 0)
{
break;
}
for (i = 0; i <= n; i++)
{
for (j = 0; j <= n; j++)
{
map[i][j] = INF;
}
}
for (int k = 0; k <n-1 ;k++)//读取题目数据,比较麻烦,注意格式
{
char s[10];
scanf("%s", s);
a = s[0] - 'A' + 1;
long long m;
scanf("%lld", &m);
while (m--)
{
scanf("%s", s);
b = s[0] - 'A' + 1;
// cout << b << endl;
long long w;
scanf("%lld", &w);
map[a][b] = w;
map[b][a] = w;
}
}
prim();
cout << ans << endl;
}
return 0;
}
Kruskal:
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <fstream>
#include <iostream>
#include <queue>
using namespace std;
long long pre[300005];
struct node//记录每一条路
{
long long u;
long long v;
long long w;
} stu[300005];
long long ans;
long long cnt;
bool cmp(node x, node y)
{
return x.w < y.w;
}
long long find(long long x)
{
if (x == pre[x])
{
return x;
}
return pre[x] = find(pre[x]);
}
void join(long long x, long long y, long long w)
{
long long ss1 = find(x);
long long ss2 = find(y);
if (ss1 != ss2)
{
pre[ss2] = ss1;
ans += w;//记录答案
cnt--;//记录道路数量。
}
}
int main()
{
long long n, i;
while (~scanf("%lld", &n))
{
if (n == 0)
{
break;
}
ans = 0;
cnt = n;
long long z = 1;
for (i = 1; i < n; i++)
{
char s[10];
scanf("%s",s);
long long u= s[0] - 'A' + 1;
long long m;
scanf("%lld", &m);
while(m--)//将所有路的情况装入结构体
{
char ss[10];
scanf("%s", ss);
long long v = ss[0] - 'A' + 1;
long long w;
scanf("%lld",&w);
stu[z].u = u;
stu[z].v = v;
stu[z].w = w;
z++;
}
}
sort(stu + 1, stu + 1 +z, cmp);//排序找到最小的路
//for (i = 1; i < z;i++)
//{
// printf("%lld %lld %lld\n", stu[i].u, stu[i].v, stu[i].w);
// }
for (i = 1; i <= n; i++)//并查集初始化
{
pre[i] = i;
}
for (i = 1; i <= z; i++)
{
join(stu[i].u, stu[i].v, stu[i].w);//判断是否连接,
if (cnt == 1)//道路连接足够,不用再继续连接
{
break;
}
}
if(cnt>1)
{
ans = -1;
}
cout << ans << endl;
}
return 0;
}
上一篇: Truck History最小生成树
下一篇: Out of Hay最小生成树
推荐阅读
-
JS使用Prim算法和Kruskal算法实现最小生成树
-
最小生成树的java实现
-
洛谷 P3366 【模板】最小生成树
-
图论小结(一)包括一些最短路,最小生成树,差分约束,欧拉回路,的经典题和变种题。强连通,双连通,割点割桥的应用。二分匹配
-
数据结构(C实现)------- 最小生成树之Kruskal算法
-
python最小生成树kruskal与prim算法详解
-
洛谷P3366 【模板】最小生成树(Boruvka算法)
-
最小生成树两个经典算法(Prime算法、Kruskal算法) - biaobiao88
-
最小生成树的两种方法(Kruskal算法和Prim算法)
-
POJ 2253 Frogger(最小生成树细节代码)