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

Arctic Network最小生成树

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

Arctic Network
原题链接https://vjudge.net/contest/352170#problem/F
Arctic Network最小生成树
Arctic Network最小生成树
有n 个信号站,有两种链接方式,一种是卫星,不需要通道,一种需要建立通道才行,问需要建立的最小通道。
Prim:
由于Prim是对于当前的点的最小值计算,所以我们需要先将最小生成树的路径求出,记录,排序,找到除去使用卫星链接的信号站的最大路径。

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <fstream>
#include <iostream>
#include <queue>
using namespace std;
const int INF = 0x3f3f3f3f;
bool vis[30005];
double dis[300005];
double map[3005][3005];
double sum[300005];
double ans;
long long z;
long long n, m;
double maxx;
struct node
{
    long long x;
    long long y;
} stu[30005];
void prim()
{
    ans = 0.0;
    long long i, j;
    for (i = 1; i <= n; i++)
    {
        vis[i] = false;
        dis[i] = map[1][i];
    }
    vis[1] = true;
    z = 1;
    for (i = 0; i < n - 1; i++)
    {
        double 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;
        sum[z] = minn;
    //    cout << minn << "   " << endl;
        z++;
        if (maxx > minn)
        {
            maxx = 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 t;
    scanf("%lld", &t);
    while (t--)
    {
        scanf("%lld %lld", &m, &n);
        long long i, j;
        for (i = 1; i <= n; i++)
        {
            scanf("%lld %lld", &stu[i].x, &stu[i].y);
        }
        for (i = 1; i <= n; i++)
        {
            for (j = 1; j <= n; j++)
            {
                map[i][j] = sqrt(1.0 * (stu[i].x - stu[j].x) * (stu[i].x - stu[j].x) + 1.0 * (stu[i].y - stu[j].y) * (stu[i].y - stu[j].y));
            }
        }
        /*  for (i = 1; i <= n; i++)
        {
            for (j = 1; j <= n; j++)
            {
                printf("%.2lf ", map[i][j]);
            }
            cout << endl;
        }*/
        prim();
        sort(sum + 1, sum + z);
      /*  for (i = 1; i <= z; i++)
        {
            printf("%.2lf ", sum[i]);
        }
        cout << endl;*/
        printf("%.2f\n", sum[n - m]);
    }
    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];
double map[3005][3005];
struct node
{
	long long u;
	long long v;
	double w;
} stu[300005];
struct id
{
	long long x;
	long long y;
} stuu[300005];
double ans;
long long cnt;
double maxx;
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, double w)
{
	long long ss1 = find(x);
	long long ss2 = find(y);
	if (ss1 != ss2)
	{
		pre[ss2] = ss1;
		ans += w;
		maxx = max(maxx, w);
		cnt--;
	}
}
int main()
{
	long long n, i, j;
	long long t;
	scanf("%lld", &t);
	while (t--)
	{
		long long sum1;
		scanf("%lld %lld", &sum1, &n);
		if (n == 0)
		{
			break;
		}
		ans = 0;
		cnt = n - sum1+1;
		maxx = -1;
		for (i = 1; i <= n; i++)
		{
			scanf("%lld %lld", &stuu[i].x, &stuu[i].y);
		}
		for (i = 1; i <= n; i++)
		{
			for (j = 1; j <= n; j++)
			{
				double dis = 1.0*sqrt(1.0*(stuu[i].x - stuu[j].x) * (stuu[i].x - stuu[j].x) + 1.0*(stuu[i].y - stuu[j].y) * (stuu[i].y - stuu[j].y));
				map[i][j] = dis;
			}
		}
	/*	for (i = 1; i <= n; i++)
		{
			for (j = 1; j <= n; j++)
			{
				printf("%.2lf ", map[i][j]);
			}
			cout << endl;
		}*/
		long long k = 0;
		for (i = 1; i <= n; i++)
		{
			for (j = i + 1; j <= n; j++)
			{
				stu[k].u = i;
				stu[k].v = j;
				stu[k].w = map[i][j];
				k++;
			}
		}
		sort(stu, stu + k, cmp);
		/*	for (i = 0; i < k; i++)
	{
		printf("*%lld %lld %lld\n", stu[i].u, stu[i].v, stu[i].w);
	}
	for (i = 0; i <= n;i++)
	{
		cout << pre[i] << endl;
	}
		cout << endl;*/
		for (i = 0; i <= n; i++)
		{
			pre[i] = i;
		}
		for (i = 0; i < k; i++)
		{
			join(stu[i].u, stu[i].v, stu[i].w);
			if (cnt == 1)
			{
				break;
			}
		}
		if (cnt > 1)
		{
			ans = -1;
		}
		printf("%.2f\n", maxx);
	}
	return 0;
}

相关标签: 最小生成树