图◆连通分量 | A1034 Head of a Gang (3

1034 Head of a Gang (30 分)

注意点

• 题目的结点给的不是编号，而是name（string），用map建立id（int）和name（string）的一一映射是很方便的！注意是双向的映射！或采用字符串哈希也可……
• 题目并没有要求输出每个gang的全体成员，因此vector保存gang全体成员id是不必要的，可以在DFS中更新person_weight更大的为head，而不必DFS后再按person_weight求head。

#include <iostream>
#include <algorithm>
#include <string>
#include <map>
#include <vector>

using namespace std;
map<int, string> id_name;
map<string, int> name_id;
int graph[2000][2000] = {0};
int NN, KK, cnt = 0;
bool visited[2000] = {false};
int person_weight[2000] = {0};
vector<int> gang;
map<string, int> head_num;

int toID(string name) {
    if (name_id.find(name) != name_id.end()) {
        return name_id[name];
    } else {
        name_id[name] = cnt;
        id_name[cnt] = name;
        return cnt++;
    }
}

void DFS(int root) {
    visited[root] = true;
    gang.emplace_back(root);
    for (int i = 0; i < cnt; ++i) {
        if (graph[root][i] > 0 && !visited[i]) {
            DFS(i);
        }
    }
}

bool cmp(int i1, int i2) {
    return person_weight[i1] > person_weight[i2];
}

int main() {
    scanf("%d%d", &NN, &KK);
    string m1, m2;
    int temp, id1, id2;
    for (int i = 0; i < NN; ++i) {
        cin >> m1 >> m2 >> temp;
        id1 = toID(m1), id2 = toID(m2);
        graph[id1][id2] = (graph[id2][id1] += temp);
        person_weight[id1] += temp;
        person_weight[id2] += temp;
    }
    int cc_cnt = 0;
    for (int i = 0; i < cnt; ++i) {
        if (!visited[i]) {
            gang.clear();
            DFS(i);
            int gang_weight = 0;
            for (auto item:gang) {
                gang_weight += person_weight[item];
            }
            if (gang_weight > 2 * KK && gang.size() > 2) {
                cc_cnt++;
                sort(gang.begin(), gang.end(), cmp);
                head_num[id_name[*gang.begin()]] = gang.size();
            }
        }
    }
    printf("%lu\n", head_num.size());
    for (auto &item:head_num) {
        cout << item.first << " " << item.second << endl;
    }
    return 0;
}

题外话

❌sorting-sets-using-std::sort
A given set has a fixed set order that cannot be changed.
set本身有序，不可用sort重排序，本来gang用了set<int>，写了cmp发现编译出错。由于本题dfs时已经保证不会重复（visited数组），直接改用vector就好。

若想实现set自定义排序的效果，方法有二：

• 用vector去重，对vector排序。vec.erase(std::unique(vec.begin(), vec.end()), vec.end());
  sort……
• supply a 2nd template parameter to std::set<>在声明set时就给出大小的定义
  若set中元素类型为结构体，在结构体中重载<即可；若不是结构体，写法如下：

struct Cmp {
    bool operator() (const int &a, const int &b) { return a > b; }
};
 set<int, myComp> s1;