欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Jungle Roads 最小生成树

程序员文章站 2022-06-16 08:57:48
...

Jungle Roads
原题链接https://vjudge.net/contest/352170#problem/A
Jungle Roads 最小生成树
Jungle Roads 最小生成树
Jungle Roads 最小生成树
也算是最小生成树的板子,对于题目给的数据要进行读取,将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;
}

相关标签: 最小生成树