团伙头目

标签：map cnt int sum 头目 nodes include 团伙

https://www.acwing.com/problem/content/1520/

思路：
先找到在一个团伙中的人（可以用树的dfs来做，也可以用并查集来做），然后遍历每一个合法的集合，找到里面的头目。

并查集的做法

#include <iostream>
#include <unordered_map>
#include <cstring>
#include <vector>
#include <algorithm>

using namespace std;

const int N = 3010;

int col[N],num[N],sum[N],con[N],n,k;
unordered_map<string,int> map;
string re_map[N];
bool st[N];

int find(int a){
    if(col[a] != a) col[a] = find(col[a]);
    return col[a];
}

int main(){
    cin >> n >> k;

    int cnt = 0,nums = 0;

    for(int i = 0; i < N; i++) col[i] = i, num[i] = 1;
    for(int i = 0; i < n; i++){
        string s1,s2;
        int val;

        cin >> s1 >> s2 >> val;
        if(!map.count(s1)) map[s1] = cnt,re_map[cnt] = s1,cnt ++;
        if(!map.count(s2)) map[s2] = cnt,re_map[cnt] = s2,cnt ++;

        int u = map[s1],v = map[s2];
        con[u] += val,con[v] += val;

        int f1 = find(u), f2 = find(v);
        if(f1 != f2){
            col[f1] = f2;
            num[f2] += num[f1];
            sum[f2] += val + sum[f1];
            nums ++;
        }else{
            //num[f2] += num[f1];
           sum[f2] += val;
        }
    }
    nums = cnt - nums;
    vector<pair<string,int>> out;

    for(int i = 0; i < cnt; i++){
        int u = find(i);

        if(st[u]) continue;
        if(num[u] < 3 || sum[u] <= k) nums--;
        else{
            int j = 0,idx = 0,val = -1;
            for(j = 0; j < cnt; j++){
                if(find(j) == u){
                    if(con[j] > val) val = con[j], idx = j;
                }
            }
            out.push_back({re_map[idx],num[u]});
        }

        st[u] = true;
    }

    sort(out.begin(),out.end());
    cout << nums << endl;
    for(auto v : out) cout << v.first << ' ' << v.second << endl;
    return 0;
}

图论的做法

#include <cstring>
#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>

using namespace std;

int n, k;
unordered_map<string, vector<pair<string, int>>> g;
unordered_map<string, int> total;
unordered_map<string, bool> st;

int dfs(string ver, vector<string> &nodes)
{
    st[ver] = true;
    nodes.push_back(ver);

    int sum = 0;
    for (auto edge : g[ver])
    {
        sum += edge.second;
        string cur = edge.first;
        if (!st[cur]) sum += dfs(cur, nodes);
    }

    return sum;
}

int main()
{
    cin >> n >> k;
    while (n -- )
    {
        string a, b;
        int t;
        cin >> a >> b >> t;
        g[a].push_back({b, t});
        g[b].push_back({a, t});
        total[a] += t;
        total[b] += t;
    }

    vector<pair<string, int>> res;
    for (auto item : total)
    {
        string ver = item.first;
        vector<string> nodes;
        int sum = dfs(ver, nodes) / 2;

        if (nodes.size() > 2 && sum > k)
        {
            string boss = nodes[0];
            for (string node : nodes)
                if (total[boss] < total[node])
                    boss = node;
            res.push_back({boss, (int)nodes.size()});
        }
    }

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

    cout << res.size() << endl;
    for (auto item : res) cout << item.first << ' ' << item.second << endl;

    return 0;
}

标签：map,cnt,int,sum,头目,nodes,include,团伙
From： https://www.cnblogs.com/xjtfate/p/16610678.html