摘要
Title: A1034 Head of a Gang (30)
Tag: 图的DFS遍历、DFS
Memory Limit: 64 MB
Time Limit: 1000 ms

A1034 Head of a Gang (30)

题意

One way that the police finds the head of a gang is to check people’s phone calls. If there is a phone call between A and B, we say that A and B is related. The weight of a relation is defined to be the total time length of all the phone calls made between the two persons. A “Gang” is a cluster of more than 2 persons who are related to each other with total relation weight being greater than a given threshold K. In each gang, the one with maximum total weight is the head. Now given a list of phone calls, you are supposed to find the gangs and the heads.
思路

思路就是按题意走，DFS找连通块，某点的关联权重就是某点的连边的权值和，将连通块的所有权重相加，如果满足gang的条件，则是一个团伙，权值最大的为boss
由于是无向图，题目给出的边u,v都得连一遍，边最后的权值需要 / 2

代码

/*
* @Author: NEFU AB-IN
* @Date: 2023-01-08 17:39:34
* @FilePath: \GPLT\A1034\A1034.cpp
* @LastEditTime: 2023-01-08 18:30:36
*/
#include <bits/stdc++.h>
using namespace std;
#define int long long
#undef int

#define SZ(X) ((int)(X).size())
#define IOS                                                                                                            \
    ios::sync_with_stdio(false);                                                                                       \
    cin.tie(nullptr);                                                                                                  \
    cout.tie(nullptr)
#define DEBUG(X) cout << #X << ": " << X << '\n'
typedef pair<int, int> PII;

const int N = 1e5 + 10, INF = 0x3f3f3f3f;

struct sa
{
    int sz;
    string boss;

    bool operator<(const sa &t) const
    {
        return boss < t.boss;
    }
};

unordered_map<string, vector<string>> g;
unordered_map<string, int> degs, st;

signed main()
{
    IOS;
    int n, k;
    cin >> n >> k;
    for (int i = 1; i <= n; ++i)
    {
        string u, v;
        int w;
        cin >> u >> v >> w;
        g[u].push_back(v);
        g[v].push_back(u);
        degs[u] += w;
        degs[v] += w;
    }

    function<void(string, vector<string> &)> dfs = [&](string u, vector<string> &nodes) { // 引用nodes，主函数的vector也会变化
        st[u] = 1;
        nodes.push_back(u);

        for (auto &v : g[u])
        {
            if (!st[v])
                dfs(v, nodes);
        }
        return;
    };

    vector<sa> ans;

    for (auto &[u, deg] : degs)
    {
        if (!st[u])
        {
            vector<string> nodes;
            dfs(u, nodes);

            int sum = 0;
            for (auto &node : nodes)
            {
                sum += degs[node];
            }
            sum /= 2;

            if (sum > k && SZ(nodes) >= 3)
            {
                string boss = nodes[0];
                for (auto node : nodes)
                {
                    if (degs[node] > degs[boss])
                        boss = node;
                }
                ans.push_back({SZ(nodes), boss});
            }
        }
    }

    sort(ans.begin(), ans.end());

    cout << SZ(ans) << '\n';
    for (auto &[sz, boss] : ans)
    {
        cout << boss << " " << sz << '\n';
    }

    return 0;
}

A1034 Head of a Gang (30)

题意

思路

代码