PAT甲级1034. Head of a Gang

题意：

警方找到一个帮派的头的一种方式是检查人民的电话。如果A和B之间有电话，我们说A和B是相关的。关系的权重被定义为两人之间所有电话的总时间长度。

“帮派”是超过2人的群体，彼此相关，总关系权重大于给定的阈值K.在每个帮派中，最大总重量的人是头。现在给了一个电话列表，你应该找到帮派和头。

输入规格：

每个输入文件包含一个测试用例。

对于每种情况，第一行分别包含两个正数N和K（均小于或等于1000），电话号码和权重。然后N行遵循以下格式：

Name1 Name2时间

其中Name1和Name2是呼叫两端的人员的姓名，“时间”是呼叫的长度。

一个名字是从A-Z中选出的三个大写字母的字符串。时间长度为不超过1000分钟的正整数。

输出规格：

对于每个测试用例，首先在一行中列出组合的总数。然后对于每个帮派，一行打印头的名字和成员的总数。

保证每个帮派的头是独一无二的。输出必须按照头部名称的字母顺序进行排序

思路：

就是相当于找有几个符合gang条件的连通分量。要求分量member2个以上。总共通话时间为k以上。dfs可以求解。

ac代码：

C++

#include<iostream>

#include<cstdio>

#include<string>

#include<algorithm>

#include<queue>

#include<vector>

#include<cstring>

#include<stdio.h>

#include<unordered_map>

#include<map>

using namespace std;

int n, k;

unordered_map<string, int> timecount;

unordered_map<string, vector<string> > link;

map<string, int> out;

map<string,bool> flag;

int idx, allweight;

string st;

void dfs(string str)

{

	flag[str] = true;

	allweight += timecount[str];

	if (timecount[str] > timecount[st]) st = str;

	for (int i = 0; i < link[str].size(); i++)

	{

		if (!flag[link[str][i]])

		{

			dfs(link[str][i]);

		}

	}

	idx++;

}

int main()

{

	cin >> n >> k;

	char a[5], b[5];

	int time;

	while (n--)

	{

		scanf("%s %s %d", a, b, &time);

		string aa = string(a), bb = string(b);

		if (timecount.find(aa) == timecount.end()) timecount[aa] = 0;

		if (timecount.find(bb) == timecount.end()) timecount[bb] = 0;

		timecount[aa] += time;

		timecount[bb] += time;

		link[aa].push_back(bb);

		link[bb].push_back(aa);

		flag[aa] = false;

		flag[bb] = false;

	}

	for (auto it = flag.begin(); it != flag.end(); it++)

	{

		if (it->second == false)

		{

			idx = 0;

			allweight = 0;

			st = it->first;

			dfs(st);

			if (idx > 2 && allweight / 2 > k)

				out[st] = idx;

		}

	}

	cout << out.size() << endl;

	for (auto it = out.begin(); it != out.end(); it++)

		cout << it->first << " " << it->second << endl;

    return 0;

}