1034 Head of a Gang (30分)

---

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

題意

找滿足以下兩個要求的幫派：
(1) 幫派人數大于2人
(2)幫派的總聯系度（通話時長）大于給定的K
除此之外找到滿足要求的幫派的老大，老大是幫派中單人聯系度最大的人。
輸出要求：
先輸出滿足要求的幫派數，
然后按幫派老大的名字的字典序輸出，同時后面輸出這個幫派的人數

思路

首先需要將每個人的名字映射出一個唯一編號（id），id和名字需要互相映射。
之后根據聯系建圖，然后基于dfs，對每個人染色，每次dfs染色的人一定是同一個幫派的人（即每次dfs給有聯系的人染同一種顏色），dfs過程中統計需要的信息，最后根據題意處理一下即可。

理清思路，題目實現起來不難，我在本題中使用了比較多STL容器來輔助處理數據。

代碼

#include <iostream> #include <string> #include <vector> #include <set> #include <map> #include <algorithm> using namespace std; const int P = 2e3+5; int id; map<int,string>mp; //id：name map<string,int>mp2;//name:id vector<int>edge[P]; int w[P]; //w[i]:編號為i的人的聯系度 set<int>st; //所有的人(里面存每個人的編號) bool vis[P]; //vis[i]標記i這個人是否被染色 int color_id; //幫派編號 vector<int>vec[P]; //每個幫派的人 int head[P]; //每個幫派里的老大 int w_total[P]; //w_total[i]:幫派編號i所有人聯系度的和（最后統計時需要/2，因為兩個人聯系是互相的，統計了兩遍） //ans struct Node {string h;int cnt;bool operator<(const Node &x)const{return h < x.h;} } node[P]; //每個人映射一個唯一id inline int get_id(string s) {if(mp2[s])return mp2[s];else{mp[++id] = s;mp2[s] = id;return id;}} //建圖 inline void add_edge(int x_id,int y_id,int v) {edge[x_id].push_back(y_id);edge[y_id].push_back(x_id);w[x_id] += v;w[y_id] += v;st.insert(x_id);st.insert(y_id); } //dfs 染色 void dfs(int x) {int cnt = edge[x].size();for(int i = 0; i < cnt; ++i){int to = edge[x][i];if(!vis[to]){vis[to] = true;vec[color_id].push_back(to);if(w[to] > w[head[color_id]]) head[color_id] = to;w_total[color_id] += w[to];dfs(to);}}return; }int main() {int n,k;cin>>n>>k;for(int i = 0; i < n; ++i){string x,y;int t;cin>>x>>y>>t;int x_id = get_id(x);int y_id = get_id(y);add_edge(x_id,y_id,t);}for(set<int>:: iterator it=st.begin(); it!=st.end(); it++){if(!vis[*it]){color_id++;vec[color_id].push_back(*it);w_total[color_id] += w[*it];head[color_id] = *it;vis[*it] = true;dfs(*it);}}int t = 0;for(int i = 1; i <= color_id; ++i){int cnt = vec[i].size();if(cnt > 2 && w_total[i]/2 > k){node[t].h = mp[head[i]];node[t].cnt = cnt;t++;}}sort(node,node+t);cout<<t<<endl;for(int i = 0; i < t; ++i){cout<<node[i].h<<" "<<node[i].cnt<<endl;}return 0; }

$Daily English

Shut out all of your past except that which help you weather your tomorrows.
放下那些不能幫助你前行的過去。

總結

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

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