英文题干

Sajin has recently delved into the study of minimum spanning trees and now he has mastered the algorithm of MST. He is eager to assess your grasp of minimum spanning tree concepts through a series of queries.

You are confronted with an weighted undirected graph that encompasses 𝑛 vertices and 𝑚 edges without any self-loops.

Sajin presents 𝑞 inquiries. For each, a vertex set 𝑆 is given. Your objective is to determine the induced subgraph of 𝑆 and find the weight of its minimum spanning tree.

A minimum spanning tree (MST) is a subset of the edges of a connected, edge-weighted graph that connects all the vertices together without any cycles and with the minimum possible total edge weight.

In the mathematical field of graph theory, an induced subgraph of a graph is another graph, formed from a subset of the vertices of the graph and all of the edges, from the original graph, connecting pairs of vertices in that subset.

If the induced subgraph of 𝑆 is disconnected, output -1.

Input:

The first line contains 3 integers — the number of points, the number of edges, and the number of queries.

Then 𝑚 lines follow, each line contains three integers — the two endpoints of the 𝑖-th edge and the edge weight.

Next 𝑞 lines, each line first contains an integer — the size of the vertex set 𝑆 for the 𝑖-th query.

Then followed by distinct integers — the numbers of the vertex set 𝑆 for the 𝑖-th query.

It is guaranteed that the sum of over all queries does not exceed .

Output:

For each query, output one integer representing the answer.

中文题干

Sajin最近深入研究了最小生成树，并且现在他已经掌握了最小生成树算法。他渴望通过一系列的查询来评估你对最小生成树概念的把握。

你面对的是一个包含n个顶点和m条边的加权无向图，没有自环。

Sajin提出了q个查询。对于每个查询，给定一个顶点集S。你的目标是确定S的诱导子图，并找出其最小生成树的权重。

最小生成树（MST）是连接所有顶点且边权重之和最小的连通带权图的边的子集，它没有环路。

在图论中，一个图的诱导子图是另一个图，由该图的顶点子集和原始图中连接该子集中顶点对的所有边形成。

如果S的诱导子图是不连通的，则输出-1。

思路

  1. 先读入边的信息，并按照边权从小到大排序

  2. 每次查询读取所涉及点所在的边，跑一个Kruskal模版即可（注意：当单次查询涉及的点过多时，直接读入所有边，然后用一个vis数组维护需要处理的元素，可以减少大规模查询时的时间复杂度）

AC代码

时间复杂度：建图复杂度。单次查询，但单次查询规模大于1000时单次复杂度为

#include <bits/stdc++.h>
#define ll long long
const int infmin = 0xc0c0c0c0;
const int infmax = 0x3f3f3f3f;
using namespace std;
const int maxn = 1e5 + 10;

inline int read()
{
    int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9')
    {
        if (ch == '-')
        {
            f = -1;
        }
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
    {
        x = (x << 1) + (x << 3) + (ch ^ 48);
        ch = getchar();
    }
    return x * f;
}

// 并查集(Kruskal用)
int group[maxn];
inline int findroot(int x)
{
    if (x == group[x])
        return group[x];
    return group[x] = findroot(group[x]);
}

struct edge
{
    int from, to, weight;

    bool operator<(const edge &other) const
    {
        return weight < other.weight;
    }
};
vector<edge> edgeSet;        // 总边集
map<pair<int, int>, int> mp; // 用于查找边权

int s[maxn];   // 查询点集
bool in[maxn]; // 需要处理的点(当询问规模过大时使用)

signed main()
{

    int n = read(), m = read(), q = read();
    for (int i = 1; i <= m; i++)
    {
        int u = read(), v = read(), w = read();
        edgeSet.push_back({u, v, w});
        mp[{u, v}] = w;
    }

    sort(edgeSet.begin(), edgeSet.end()); // 边权从小到大排序

    while (q--)
    {
        memset(in, 0, sizeof(in));  // 初始化用memset速度高于for循环
        int k = read();
        for (int i = 1; i <= k; i++)
        {
            s[i] = read();
            group[s[i]] = s[i];
            in[s[i]] = 1;
        }

        vector<edge> vec; // 本轮建立MST所用到的边集
        if (k < 1000)
        {
            for (int from = 1; from <= k; from++)
            {
                for (int to = 1; to <= k; to++)
                {
                    if (mp.find({s[from], s[to]}) != mp.end())
                    // if (mp[{s[from], s[to]}] != 0)  // 直接比较会超时，需要用find
                    {
                        vec.push_back({s[from], s[to], mp[{s[from], s[to]}]});
                    }
                }
            }
            sort(vec.begin(), vec.end());
        }
        else
        {
            vec = edgeSet;
        }

        // Kruskal模版
        ll res = 0, cnt = 0;
        for (int i = 0; i < vec.size(); i++)
        {
            int a = vec[i].from, b = vec[i].to, w = vec[i].weight;
            if (in[a] && in[b])
            {
                a = findroot(a), b = findroot(b);
                if (a != b) // 如果两个连通块不连通，则将这两个连通块合并
                {
                    group[a] = b;
                    res += w;
                    cnt++;
                }
            }
        }

        if (cnt < k - 1)
            res = -1;

        printf("%lld\n", res);
    }

    return 0;
}