本文共 1770 字，大约阅读时间需要 5 分钟。
题意：
给出n次通话记录，当通话的人数超过2人并且通话总时长超过k时，这些人就是犯罪团伙，其中通话时间最大的人是头目，要求按字母序输出头目和团伙人数
思路：
就是并查集，将两两通话的人关联在一起，因为通话的人的姓名是按三位字母给出的，所以要离散化，并且对应要用一些STL保存映射。我自己写的时候有两个点没过，后来改过了，错误原因写在下面注释里了。网上的代码也有用DFS找连通分量做的。
#include #include #include #include #include #include using namespace std;const int INF = 0xfffff;const int maxn = 2010; //这里开1005会出现段错误,因为是n个通话可能有2n个人map gang;map gangName;int gangTime[maxn];int p[maxn];int n, k,pos=0;vector head[maxn];set res;void init() { for (int i = 0; i < maxn; i++) { p[i] = i; head[i].push_back(i); }}int find(int x) { if (x == p[x]) return x; return p[x] = find(p[x]);}void merge(int x, int y) { x = find(x); y = find(y); if (x != y) { p[x] = y; for (auto i = head[x].begin(); i != head[x].end(); i++) { head[y].push_back(*i); } head[x].clear(); //这里必须清零 }}int main() { scanf("%d%d", &n, &k); init(); for (int i = 0; i < n; i++) { string name1, name2; int time; cin >> name1 >> name2 >> time; if (gang.find(name1) == gang.end()) { gang[name1] = pos; gangName[pos++] = name1; } if (gang.find(name2) == gang.end()) { gang[name2] = pos; gangName[pos++] = name2; } gangTime[gang[name1]] += time; gangTime[gang[name2]] += time; merge(gang[name1], gang[name2]); } for (int i = 0; i < pos; i++) { if (head[i].size() > 2) { int maxTime = -1, index; int totalTime = 0; for (auto x : head[i]) { if (maxTime < gangTime[x]) { maxTime = gangTime[x]; index = x; } totalTime += gangTime[x]; } if (totalTime > 2*k) { res.insert(gangName[index]); } } } if (res.empty()) cout << 0 << endl; else { cout << res.size() << endl; for (auto x : res) { int h = find(gang[x]); cout << x << " " << head[h].size() << endl; } } return 0;}
转载于:https://www.cnblogs.com/seasonal/p/10343631.html