Constructing Roads
Original question link https://vjudge.net/competition/352170 "problem / C


The topic gives the relationship of all roads, and the roads that have been repaired, to find the minimum value of the rest roads.
It's better to read the map directly. When reading the repaired Road, change the weight value of the repaired road to 0, and calculate normally,
Prim:

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <fstream>
#include <iostream>
#include <queue>
using namespace std;
const int INF = 0x3f3f3f3f;
long long map[305][305];
long long dis[300005];
bool vis[300005];
long long ans;
long long n;
void prim()
{
    ans = 0;
    long long i, j;
    for (i = 1; i <= n; i++)
    {
        dis[i] = map[1][i];
        vis[i] = false;
    }
    vis[1] = true;
    for (i = 0; i < n - 1; 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;
            }
        }
        // cout << "***" << endl;
        //  for (j = 1; j <= n; j++)
        //  {
        //      cout << dis[j] << " ";
        //   }
        //    cout << endl;
        if (minn == INF)
        {
            ans = -1;
            return;
        }
        ans += minn;
        vis[p] = true;
        for (j = 1; j <= n; j++)
        {
            if (!vis[j] && dis[j] > map[p][j])
            {
                dis[j] = map[p][j];
            }
        }
    }
    return;
}
int main()
{
    long long i, j;
    scanf("%lld", &n);
    for (i = 0; i <= n; i++)
    {
        for (j = 0; j <= n; j++)
        {
            map[i][j] = INF;
        }
    }
    for (i = 1; i <= n; i++)
    {
        for (j = 1; j <= n; j++)
        {
            scanf("%lld", &map[i][j]);
            //   if (i == j)
            //  {
            //      map[i][j] = INF;
            // }
        }
    }

    long long m;
    scanf("%lld", &m);
    while (m--)
    {
        long long a, b;
        scanf("%lld %lld", &a, &b);//Read the connected path.
        map[a][b] = 0;
        map[b][a] = 0;
    }
    // for (i = 1; i <= n; i++)
    // {
    //for (j = 1; j <= n; j++)
    //{
    //     printf("%5lld ", map[i][j]);
    ///   }
    //     cout << endl;
    //   }
    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];
long long map[3005][3005];
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;
	scanf("%lld", &n);
	ans = 0;
	cnt = n;
	long long m, j;
	for (i = 0; i <= n; i++)
	{
		pre[i] = i;
	}
	for (i = 1; i <= n; i++)
	{
		for (j = 1; j <= n; j++)
		{
			scanf("%lld", &map[i][j]);
		}
	}
	long long t, a, b;
	scanf("%lld", &t);
	while (t--) //Clear the length of the road that has been built and connect it directly.
	{
		scanf("%lld %lld", &a, &b);
		join(a, b, 0);
		map[a][b] = 0;
		map[b][a] = 0;
	}
	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 < k; 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;
}