題干：

One way that the police finds the head of a gang is to check people's phone calls. If there is a phone call between?A?and?B, we say that?A?and?B?is related. The weight of a relation is defined to be the total time length of all the phone calls made between the two persons. A "Gang" is a cluster of more than 2 persons who are related to each other with total relation weight being greater than a given threshold?K. In each gang, the one with maximum total weight is the head. Now given a list of phone calls, you are supposed to find the gangs and the heads.

Input Specification:

Each input file contains one test case. For each case, the first line contains two positive numbers?N?and?K?(both less than or equal to 1000), the number of phone calls and the weight threthold, respectively. Then?N?lines follow, each in the following format:

Name1 Name2 Time

where?Name1?and?Name2?are the names of people at the two ends of the call, and?Time?is the length of the call. A name is a string of three capital letters chosen from?A-Z. A time length is a positive integer which is no more than 1000 minutes.

Output Specification:

For each test case, first print in a line the total number of gangs. Then for each gang, print in a line the name of the head and the total number of the members. It is guaranteed that the head is unique for each gang. The output must be sorted according to the alphabetical order of the names of the heads.

Sample Input 1:

8 59 AAA BBB 10 BBB AAA 20 AAA CCC 40 DDD EEE 5 EEE DDD 70 FFF GGG 30 GGG HHH 20 HHH FFF 10

Sample Output 1:

2 AAA 3 GGG 3

Sample Input 2:

8 70 AAA BBB 10 BBB AAA 20 AAA CCC 40 DDD EEE 5 EEE DDD 70 FFF GGG 30 GGG HHH 20 HHH FFF 10

Sample Output 2:

0

題目大意：

警察發現團伙頭目的一種方法是檢查人們的電話。如果a和B之間有電話，我們說a和B是相關的。關系的權重被定義為兩個人之間所有通話的總時間長度。一個“團伙”是一個由2個以上的人組成的群體，他們相互之間有關聯，總關聯權重大于給定的閾值K。在每一組中，總重量最大的是頭部。現在給出一個電話列表，你應該找到團伙和頭目。

解題報告：

并查集維護集合元素個數，集合的權值和，每個元素的權值即可。

最后按要求輸出答案。

AC代碼：

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<stack> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define FF first #define SS second #define ll long long #define pb push_back #define pm make_pair using namespace std; typedef pair<int,int> PII; const int MAX = 2e5 + 5; map<string,int> mp; string NAME[MAX]; char s1[5],s2[5]; int n,K; int tot,f[MAX],num[MAX],V[MAX]; int val[MAX]; int getf(int v) {return f[v] == v ? v : f[v] = getf(f[v]); } void merge(int u,int v,int w) {int t1 = getf(u),t2 = getf(v);if(t1 == t2) {V[t1] += w;return;}f[t2] = t1;num[t1] += num[t2];V[t1] += V[t2]+w; } vector<int> boss; PII pr[MAX]; struct Node {string name;int num; } ans[MAX]; int top; bool cmp(Node a,Node b) {return a.name < b.name; } int main() {cin>>n>>K;for(int w,i = 1; i<=n; i++) {scanf("%s%s%d",s1,s2,&w);if(mp.find(s1) == mp.end()) mp[s1] = ++tot,NAME[tot] = s1,num[tot] = 1,f[tot] = tot;if(mp.find(s2) == mp.end()) mp[s2] = ++tot,NAME[tot] = s2,num[tot] = 1,f[tot] = tot;val[mp[s1]] += w;val[mp[s2]] += w;merge(mp[s1],mp[s2],w);}for(int i = 1; i<=tot; i++) {if(f[i] == i && num[i] > 2 && V[i] > K) boss.push_back(i),pr[i].first = i,pr[i].second = val[i]; }for(int i = 1; i<=tot; i++) {int tar = getf(i);if(val[i] > pr[tar].second) {pr[tar].first = i; pr[tar].second = val[i];}}for(auto x : boss) {ans[++top].name = NAME[pr[x].first];ans[top].num = num[x];}sort(ans+1,ans+top+1,cmp);printf("%d\n",top);for(int i = 1; i<=top; i++) {cout << ans[i].name << " " << ans[i].num << endl;}return 0 ; }

?

總結

以上是生活随笔為你收集整理的【PAT - 甲级1034】Head of a Gang (30分)（并查集）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。