PTA A_1034 Head of a Gang

798236606

传送门：https://pintia.cn/problem-sets/9 ... /994805456881434624

解：
图的DFS +求边和

#include <iostream>
#include <string>
#include <map>

using namespace std;

const int maxn = 2010;

int G[maxn][maxn], k, num, m, total, max_id;
int weight[maxn];
bool vis[maxn];
map<string, int> s2i, gang;
map<int, string> i2s;

int add_name(string s)
{
    int id = s2i[s];

    if (!id)
    {
        s2i[s] = ++num;
        i2s[num] = s;
        return num;
    } 

    return id;
}

void DFS(int id)
{
    if (!vis[id]) m++;//计算同伙人数
    if (weight[id] > weight[max_id]) max_id = id;//查找头目

    vis[id] = true;
    // cout << i2s[id] << weight[id] << endl;
    for (int i = 1; i <= num; i++)
        if (G[id][i]) 
        {
            // cout << i2s[id] << "--" << i2s[i] << "=" << G[id][i] << endl;
            total += G[id][i];//一个团伙的总通话时间
            G[id][i] = G[i][id] = 0;//切断已经计算过的边
            DFS(i);
        }
}

int DFS_traverse(void)
{
    int n = 0;

    for (int i = 1; i <= num; i++)
    {
        if (!vis[i])
        {
            m = total = 0;
            max_id = i;

            DFS(i);

            if (m > 2 && total > k && ++n) gang[i2s[max_id]] = m;
            // cout << "max_id = " << i2s[max_id] << "total = " << total << "n = " << n << endl;
        }
    }

    return n;
}

int main() {
    // freopen("input.txt", "r", stdin);
    int n;

    cin >> n >> k;

    while (n--)
    {
        string s1, s2;
        int w;

        cin >> s1 >> s2 >> w;
        
        int n1 = add_name(s1);
        int n2 = add_name(s2);
        weight[n1] += w;
        weight[n2] += w;
        G[n1][n2] += w;
        G[n2][n1] += w;
    }

    printf("%d\n", DFS_traverse());

    for (map<string, int>::iterator it = gang.begin(); it != gang.end(); ++it)
        cout << it->first << " " << it->second << endl;

    return 0;
}