(重要！） 图的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\n", Gang.size());
for (auto it = Gang.begin();it != Gang.end();it++)
cout << it->first << " " << it->second << endl;
return 0;
}
