题目的大意是有不同的人通话，当人数超过2个，并且通话时间大于K，那么我们就
称它为gang，在每一个gang中某个人的通话时间最多，就把最多的那个人称为head
现在让我们找有多少个gang，每一个gang中的head是谁，这个gang里面有多少人。
很明显的是，这需要建图，但都是人名，字符串，建图的时候需要把字符串转换成数字，方便建图.
int tobecomeid(string name)
{
if(nametoid.count(name))
{
return nametoid[name];
}
nametoid[name]=cnt;
idtoname[cnt]=name;
cnt++;
return nametoid[name];
}
边权也要注意，需要把两个人每次的通话时间都加起来，
The weight of a relation is defined to be the total time length of all the phone calls made between the two persons.
采用邻接矩阵建图，因为题目上说通话记录最多有1000，那么最坏的情况就是每次通话的两个人都不同，那么有2000人，建图是【2000】【2000】，内存大小是可以接受的。
因此建图已经明确了：
cin>>N>>K;
for(int i=0;i<N;i++)
{
string name1;
string name2;
int time;
cin>>name1>>name2>>time;
int id1=tobecomeid(name1);
int id2=tobecomeid(name2);
a[id1][id2]+=time;
a[id2][id1]+=time;
weight[id1]+=time;
weight[id2]+=time;
}
而我们只需要用dfs在图中找连通分量，只需要保证这个连通分量中的成员个数>2,
总的通话时间>K，即是符合条件的gang，同时我们在dfs找连通分量的过程中找最大的weight作为head，即可满足题意。
void dfs(int x,int &totalweight,int &member,int &head)
{
vis[x]=true;
member++;
totalweight+=weight[x];
if(weight[head]<weight[x])
{
head=x;
}
for(int i=0;i<cnt;i++)
{
if(vis[i]==0&&a[x][i]!=0)
{
dfs(i,totalweight,member,head);
}
}
}
for(int i=0;i<cnt;i++)
{
if(vis[i]==0)
{
int head=i;
int totalweight=0;
int member=0;
dfs(i,totalweight,member,head);
//这样就得到一个连通分量我们来判断它是不是
//符合条件
if(totalweight/2>K&&member>2)
{
ans[idtoname[head]]=member;
}
}
}
注意要采用值传递，因为在dfs遍历一次后我们要判断该连通分量是否符合题意
if(totalweight/2>K&&member>2)
{
//说明符合条件
//但不代表可以直接输出
ans[idtoname[head]]=member;
}
采用上述的方法
如果符合条件那么我们就需要保存这个gang的head，和它的总的成员数member，
但是我们不能直接输出，需要把数字再重新转化成字符串（名字）(在转数字的函数中可以同时做这件事）
int tobecomeid(string name)
{
if(nametoid.count(name))
{
return nametoid[name];
}
nametoid[name]=cnt;
idtoname[cnt]=name;
cnt++;
return nametoid[name];
}
题目上说要按照字典顺序输出，因此我们再用一个map来保存这些字符串和它对应的成员数
最后按照题意输出即可。
map<string,int> ans;
cout<<ans.size()<<endl;
for(auto it: ans)
{
cout<<it.first<<" "<<it.second<<endl;
}
完整代码如下：
#include <iostream>
#include <limits.h>
#include <cstring>
#include <queue>
#include <unordered_map>
#include <algorithm>
#include <cmath>
#include <vector>
#include <map>
using namespace std;
int N;
int K;
int a[2005][2005];
int weight[2005];
unordered_map<string,int> nametoid;
unordered_map<int,string> idtoname;
int cnt;
bool vis[2005];
int tobecomeid(string name)
{
if(nametoid.count(name))
{
return nametoid[name];
}
nametoid[name]=cnt;
idtoname[cnt]=name;
cnt++;
return nametoid[name];
}
void dfs(int x,int &totalweight,int &member,int &head)
{
vis[x]=true;
member++;
totalweight+=weight[x];
if(weight[head]<weight[x])
{
head=x;
}
for(int i=0;i<cnt;i++)
{
if(vis[i]==0&&a[x][i]!=0)
{
dfs(i,totalweight,member,head);
}
}
}
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>N>>K;
for(int i=0;i<N;i++)
{
string name1;
string name2;
int time;
cin>>name1>>name2>>time;
int id1=tobecomeid(name1);
int id2=tobecomeid(name2);
a[id1][id2]+=time;
a[id2][id1]+=time;
weight[id1]+=time;
weight[id2]+=time;
}
//图已经建好
map<string,int> ans;
for(int i=0;i<cnt;i++)
{
if(vis[i]==0)
{
int head=i;
int totalweight=0;
int member=0;
dfs(i,totalweight,member,head);
//这样就得到一个连通分量我们来判断它是不是
//符合条
if(totalweight/2>K&&member>2)
{
//说明符合条件
//但不代表可以直接输出
ans[idtoname[head]]=member;
}
}
}
cout<<ans.size()<<endl;
for(auto it: ans)
{
cout<<it.first<<" "<<it.second<<endl;
}
return 0;
}
虽然题目的本质只是一个建图+dfs找连通分量，但过程还是需要考虑很多的条件，较复杂。