ACM template

describe

Answer key

If you see clearly the meaning of the question, it is actually easy to think of the idea. The first priority condition is that the maximum edge weight of the generated tree must be minimal. The second priority condition is that the total weight and requirement of the spanning tree are maximum. To analyze the first condition, we need to use Kruskal_0 to find the minimum spanning tree, and record the maximum edge weight MAXW in this case; Then analyze the second condition, we can naturally think of the maximum spanning tree, but the edge of the maximum spanning tree cannot be greater than MAXW, so we need to use Kruskal_1 function, which is a maximum spanning tree with the maximum edge weight limit code segment, return the spanning tree weight sum.

To clarify, the Kruskal algorithm is used because the difference between the algorithm’s minimum and maximum spanning trees lies in the sorting part. Of course, we can also extract the sorting part and unified sorting scheme, but the internal traversal direction should be appropriately changed. Pay attention to what the return value returns.

code

#include <iostream>
#include <algorithm>
#include <cstring>

typedef long long ll;

using namespace std;

const int MAXN = 1e5 + 10;
const int MAXM = 2 * MAXN;

int F[MAXN];    / / and set
int MAXW = 0;

struct edge
{
    int u;      / / starting point
    int v;      / / the end
    int w;      / / has a weight
} Edge[MAXM];   // Store edge information

int tol = 0;    / / the number of edges

void addEdge(int u, int v, int w)
{
    Edge[tol].u = u;
    Edge[tol].v = v;
    Edge[tol++].w = w;
    return ;
}

// From small to large
bool cmp_0(edge a, edge b)
{
    return a.w < b.w;
}

// From large to small
bool cmp_1(edge a, edge b)
{
    return a.w > b.w;
}

int find(int x)
{
    if (F[x] == - 1)
    {
        return x;
    }
    else
    {
        return F[x] = find(F[x]); }}// Minimum spanning tree
int Kruskal_0(int n)  // Pass in the number of points and return the maximum edge weight of the minimum spanning tree, or -1 if disconnected
{
    memset(F, - 1.sizeof(F));
    sort(Edge, Edge + tol, cmp_0);
    int cnt = 0;    // Count the number of edges added
    int ans = 0;
    for (int i = 0; i < tol; i++)
    {
        int u = Edge[i].u;
        int v = Edge[i].v;
        int w = Edge[i].w;
        int tOne = find(u);
        int tTwo = find(v);
        if(tOne ! = tTwo) {if (ans < w)
            {
                ans = w;
            }
            F[tOne] = tTwo;
            cnt++;
        }
        if (cnt == n - 1)
        {
            break; }}if (cnt < n - 1)
    {
        return - 1;
    }
    else
    {
        returnans; }}// Maximum spanning tree (with maximum edge weights)
ll Kruskal_1(int n)  // Pass in the number of points and return the weight of the maximum spanning tree, or -1 if not connected
{
    memset(F, - 1.sizeof(F));
    sort(Edge, Edge + tol, cmp_1);
    int cnt = 0;    // Count the number of edges added
    ll ans = 0;
    for (int i = 0; i < tol; i++)
    {
        if (Edge[i].w > MAXW)
        {
            continue;
        }
        int u = Edge[i].u;
        int v = Edge[i].v;
        int w = Edge[i].w;
        int tOne = find(u);
        int tTwo = find(v);
        if(tOne ! = tTwo) { ans += w; F[tOne] = tTwo; cnt++; }if (cnt == n - 1)
        {
            break; }}if (cnt < n - 1)
    {
        return - 1;
    }
    else
    {
        returnans; }}int main(int argc, const char * argv[])
{
// freopen("/Users/zyj/Desktop/input.txt", "r", stdin);

    int N, M;
    cin >> N >> M;

    int A, B, V;
    for (int i = 0; i < M; i++)
    {
        cin >> A >> B >> V;
        addEdge(A, B, V);
    }

    MAXW = Kruskal_0(N);

    ll ans = Kruskal_1(N);

    cout << ans << '\n';

    return 0;
}
Copy the code

reference

Minimum Spanning Tree