论坛 › C\C++交流 › PTA A_1034 Head of a Gang

798236606 发表于 2020-2-18 09:55:29

PTA A_1034 Head of a Gang

本帖最后由 798236606 于 2020-2-18 09:59 编辑

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

解：
图的DFS +求边和
#include <iostream>
#include <string>
#include <map>

using namespace std;

const int maxn = 2010;

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

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

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

    return id;
}

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

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

int DFS_traverse(void)
{
    int n = 0;

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

            DFS(i);

            if (m > 2 && total > k && ++n) gang] = m;
            // cout << "max_id = " << i2s << "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 += w;
      weight += w;
      G += w;
      G += 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;
}

查看完整版本: PTA A_1034 Head of a Gang