PAT甲级1034 Head of a Gang (30 分)题解

$\quad$这个题虽然只是图的遍历问题，但写程序要求较高，几点需要注意

• 给出的人员姓名不是数字是字符串，需要建立姓名到索引和索引到姓名的映射，方便建图和后续处理
• 需要记录每个人通话总时间，团队通话总时间就是该团队内所有人通话时间和的一半
• 1000条通话记录最多可能有2000人，故需要开辟大于2000的空间，不然有个测试点会显示段错误

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;

const int maxn = 2001; // 1000条记录最多2000人
vector<int> E[maxn];
int call[maxn];  // 记录每个人通话时间
int vis[maxn];
struct Gang{ //记录每一个团伙信息
	string head;
	int num=0, totalCall=0, flag=0;
}gang[maxn];
int callMax = 0;
map<string, int> mp;  // 姓名到编号的索引
map<int, string> rmp;  // 编号到姓名的索引
void dfs(int u, Gang &g)
{
	vis[u] = 1;
	g.num++, g.totalCall+=call[u];  // 更新团伙信息
	if(call[u]>callMax) callMax=call[u], g.head=rmp[u];
	for (int i = 0; i < E[u].size(); ++i){
		int v = E[u][i];
		if(vis[v]==0) dfs(v, g);
	}
}
bool cmp(const Gang &g1, const Gang &g2) { return g1.head<g2.head; }
int main(int argc, char const *argv[])
{
	int N, K; cin >> N >> K;
	int num = 0;
	for (int i = 0; i < N; ++i){
		string a, b;
		int time;
		cin >> a >> b >> time;
		if(mp.count(a)==0) rmp[num]=a, mp[a] = num++;
		if(mp.count(b)==0) rmp[num]=b, mp[b] = num++;
		call[mp[a]] += time, call[mp[b]] += time;  // 更新通话时间
		E[mp[a]].push_back(mp[b]);
		E[mp[b]].push_back(mp[a]);
	}
	int index = 0;
	for (int i = 0; i < num; ++i){
		callMax = 0;  // 每一次dfs前置最大通话时间为0 
		if(vis[i]==0) dfs(i, gang[index++]);
	}
	sort(gang, gang+index, cmp);  // 按照领头人姓名排序
	int res = 0;  // 记录合法的团伙数
	for (int i = 0; i < index; ++i){
		if(gang[i].num<=2 || gang[i].totalCall/2<=K) continue;  // 不合法
		gang[i].flag=1, res++;
	}
	cout << res << endl;
	for (int i = 0; i < index; ++i){
		if(gang[i].flag==1) cout << gang[i].head << " " << gang[i].num << endl;
	}
	return 0;
}