题目
解决
思路
因为结点的最大值不大，所以用邻接矩阵实现图（一般不超过1000个点的时候用邻接矩阵）考虑到名字和编号的映射，用Map实现，所以需要map<string, int> name2id， 和map<int, string> id2name;在DFS的过程中，要计算每个类的大小（人数），这个类里面weight最大的人，这个类的总weight，所以DFS需要以上3个参数和当前访问结点，为了修改这三个参数，传入的应该是地址。注意点：
通话记录最多1000条，所以最多有2000人，而不是1000人。map<type1, type2>是按照type1从小到大排序的，用这个可以解决题目要求的输出按字典序大小递增的要求。numMember初始值为0，因为在DFS的第一个顶点处就++了因为图中可能出现环，为了边权不被漏加，需要先累加边权然后再考虑递归DFS的问题，但是这样做可能会出现重复访问的问题，所以再累加之后将图中对应的两个边置零。
实现
Code1
#include<cstdio>
#include<iostream>
#include<string>
#include<map>
using namespace std;
const int MAXV = 2010;
const int INF = 1000000000;
map<string, int> gang; //head->人数
map<string, int> name2id;
map<int, string> id2name;
int n, k;
int numPerson = 0; //总人数
int G[MAXV][MAXV] = {0};
int weight[MAXV] = {0}; //每个人的权重
bool vis[MAXV] = {false};
void DFS(int now, int& head, int& numMember, int& totalWeight){
numMember++;
vis[now] = true;
if(weight[now] > weight[head]){
head = now;
}
for(int i=0; i<numPerson; i++){
if(G[now][i] > 0){
totalWeight += G[now][i];
G[now][i] = 0;
G[i][now] = 0;
if(vis[i] == false){
DFS(i, head, numMember, totalWeight);
}
}
}
}
void DFSTravel(){
for(int i=0; i<numPerson; i++){
if(vis[i] == false){
int head = i;
int numMember = 0;
int totalWeight = 0;
DFS(i, head, numMember, totalWeight);
if(numMember > 2 && totalWeight > k){ // 说明这个是gang
gang[id2name[head]] = numMember;
}
}
}
}
int getId(string str){
if(name2id.find(str) != name2id.end()){
return name2id[str];
}else{
name2id[str] = numPerson;
id2name[numPerson] = str;
return numPerson++;
}
}
int main(){
scanf("%d%d", &n, &k);
string name1, name2;
int time;
for(int i=0; i<n; i++){
cin >> name1 >> name2 >> time;
//每个人增加相应的time
int id1 = getId(name1);
int id2 = getId(name2);
weight[id1] += time;
weight[id2] += time;
G[id1][id2] += time;
G[id2][id1] += time;
}
DFSTravel();
cout << gang.size() << endl;
for(map<string, int>::iterator it=gang.begin(); it!=gang.end(); it++){
cout << it->first << " " << it->second << endl;
}
}
