[PAT] A1034 Head of a Gang

(重要！）
图的DFS遍历；map的使用

思路

方法一

算法笔记第355页

方法二

法一中的点权和边权其实是一个东西，用一个map存起来就好，输入的时候如果a和b有通话，则a的点权和b的点权都加上通话时长，且将一条边插入图中（无需知道边长，图用map<string, vector>保存，这样直接以人名对应，比较方便。vector里存的是与键有通话记录的人名，插入时记得遍历一次若无记录才插入，避免重复）。一次DFS遍历得出一个连通图的成员，用vector保存人名，这样顺便也可直接获取人数。连通图各个结点的点值相加再除以二即整个连通图的通话时长总和，这样也避免了遍历图计算边权重复的问题。最后将头目姓名和人数存在一个map中，map会自动排序，直接输出即可。

AC代码

方法一

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<iostream>
#include<string>
#include<string.h>
#include<vector>
#include<map>
using namespace std;
#define MAX 2010
map<string, int>strtoint;
map<int, string>inttostr;
map<string, int>gang;
int G[MAX][MAX] = { 0 };
int weight[MAX] = { 0 };
bool vis[MAX] = { false };
int n, threshold;
int numPerson = 0;
void DFS(int now, int& head, int& member, int& total) {
	vis[now] = true;
	member++;
	if (weight[now] > weight[head])
		head = now;
	for (int i = 0;i < numPerson;i++) {
		if (G[now][i] > 0) {
			total += G[now][i];
			G[now][i] = G[i][now] = 0;
			if (vis[i] == false)
				DFS(i, head, member, total);
		}
	}
}
void DFSTrave() {
	int i;
	for (i = 0;i < numPerson;i++) {
		if (vis[i] == false) {
			int head = i, member = 0, total = 0;
			DFS(i, head, member, total);
			if (member > 2 && total > threshold) {
				gang[inttostr[head]] = member;
			}
		}
	}
}
int change(string str) {
	if (strtoint.find(str) != strtoint.end()) {
		return strtoint[str];
	}
	else {
		strtoint[str] = numPerson;
		inttostr[numPerson] = str;
		return numPerson++;
	}
}
int main() {
	scanf("%d%d", &n, &threshold);
	int i;
	for (i = 0;i < n;i++) {
		string str1, str2;
		int w;
		cin >> str1 >> str2 >> w;
		int id1 = change(str1);
		int id2 = change(str2);
		G[id1][id2] += w;
		G[id2][id1] += w;
		weight[id1] += w;
		weight[id2] += w;
	}
	DFSTrave();
	map<string, int>::iterator it;
	cout << gang.size() << endl;
	for (it = gang.begin();it != gang.end();it++) {
		cout << it->first << " " << it->second << endl;
	}
	return 0;
}

方法二

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<cstdio>
#include<string>
#include<map>
#include<vector>
#include<algorithm>
using namespace std;
map<string, int>Gang;//键：头目名；值：人数（满足人数>2,并且通话总时长大于给定值）
map<string, vector<string>>mp;
map<string, int>vis;
vector<string>tmember;//临时存储每个连通图的成员
map<string, int>headtime;//每个人的通话总时长
void DFS(string s) {
	vis[s] = true;
	tmember.push_back(s);
	for (int i = 0;i < mp[s].size();i++) 
		if (vis[mp[s][i]] == false) DFS(mp[s][i]);
}
int main() {
	int i, j, n, time, threshold;
	string head;
	scanf("%d%d", &n, &threshold);
	for (i = 0;i < n;i++) {
		string name1, name2;
		cin >> name1 >> name2 >> time;
		headtime[name1] += time;
		headtime[name2] += time;
		vis[name1] = vis[name2] = false;
		for (j = 0;j < mp[name1].size();j++) 
			if (mp[name1][j] == name2)
				break;
		if (j == mp[name1].size())
			mp[name1].push_back(name2);
		for (int j = 0;j < mp[name2].size();j++) 
			if (mp[name2][j] == name1)
				break;
		if (j == mp[name2].size())
			mp[name2].push_back(name1);
	}
	for (auto it = mp.begin();it != mp.end();it++) {
		if (vis[it->first] == false) {
			tmember.clear();
			DFS(it->first);
			int sumtime = 0;
			for (i = 0;i < tmember.size();i++)
                                sumtime += headtime[tmember[i]];
			sumtime = sumtime / 2;
			if (sumtime > threshold && tmember.size() > 2) {
				time = headtime[tmember[0]];
                                head = tmember[0]; 
				for (i = 1;i < tmember.size();i++) //找头目：通话多的。
					if (headtime[tmember[i]] > time) {
						head = tmember[i];
						time = headtime[tmember[i]];
					}
				Gang[head] = tmember.size();
			}
		}
	}
	printf("%d
", Gang.size());
	for (auto it = Gang.begin();it != Gang.end();it++)
		cout << it->first << " " << it->second << endl;
	return 0;
}