ACM模版

描述

题解

这道题如果看清楚题意，那其实思路很容易想起来。分析题意可以得知，答案要求满足两个条件：
第一优先条件是，生成的树的最大边权必须最小；
第二优先条件是，生成树的总权值和要求最大。
分析第一个条件，我们需要使用Kruskal_0来求最小生成树，并且记录下来该种情况下，最大的边权MAXW；
接着分析第二个条件，我们顺理成章的可以想到最大生成树，但是这个最大生成树的边不能大于MAXW，所以我们需要用到Kruskal_1函数，这是一个求有最大边权限制的最大生成树代码段，返回生成树的权值和。

这里说明一下，之所以都使用Kruskal算法是因为该算法求最小和最大生成树的差异就在于排序部分，当然，我们也可以将排序部分抽离出来，统一排序方案，不过内部遍历方向要适当改变。要注意返回值返回的是什么。

代码

#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];    // 并查集
int MAXW = 0;

struct edge
{
    int u;      // 起点
    int v;      // 终点
    int w;      // 权值
} Edge[MAXM];   // 存储边信息

int tol = 0;    // 边数

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

// 从小到大排
bool cmp_0(edge a, edge b)
{
    return a.w < b.w;
}

// 从大到小排
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]);
    }
}

// 最小生成树
int Kruskal_0(int n)  // 传入点数，返回最小生成树的最大边权值，如果不连通返回-1
{
    memset(F, -1, sizeof(F));
    sort(Edge, Edge + tol, cmp_0);
    int cnt = 0;    // 计算加入边数
    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
    {
        return ans;
    }
}

// 最大生成树（有最大边权限制）
ll Kruskal_1(int n)  // 传入点数，返回最大生成树的权值，如果不连通返回-1
{
    memset(F, -1, sizeof(F));
    sort(Edge, Edge + tol, cmp_1);
    int cnt = 0;    // 计算加入边数
    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
    {
        return ans;
    }
}

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;
}

参考

《最小生成树》