题目连接
题目意思
警察找到帮派头目的一种方法是检查人们的电话。 如果A和B之间有电话，我们说A和B是相关的。 关系的权重被定义为两个人之间所有电话的总时间长度。 “帮派”是指两个以上人群相互关联，总关系重量大于给定阈值K的集群。每个团伙中，总重量最大者是头部。 现在给出一个电话列表，你应该找到帮派和头部。
总结
1。在一堆人中找出来gang和head of gang
2。这一度人中人与人之间如果有电话calls则认为是彼此联系，联系的权重是通话时间
3。gang是满足人数大于2，gang中总通话大于阈值
分析题目
1.肯定是找联通分量，连通分量用BFS
2.要找联通分量要构建图，怎么构建。题目中说的是两个人的名字，那么需要把名字转换为数字，怎么转化？如果两个点有连线，权重是1，还是通话总时长？
3.如果这个连通分量重有环，怎么求总time，难道要遍历每一条边？？
做题思路
1.构建图，在构件图时要将string转为int，那么key -value是谁？map，所以用两个map，记录string-id和id-string
2.对于每个节点，要记录他的total time，用于找head
3.求连通分量中total time时，可以发现等于这个连通分量重所有点的total time之和除以2
题目难点
1。string-int转化，可以用两个map
2。有环连通分量的total time计算
代码献上
#include <iostream>#include <map>#include <string>#include <queue>#include <algorithm>/* run this program using the console pauser or add your own getch, system("pause") or input loop */using namespace std;int N,K;//N 最大为1000，两个名字不就是2000 const int MAX = 2000+5; int graph[MAX][MAX]; int weight[MAX];//0表示不再，-1表示在未访问，1表示访问 bool visited[MAX] = {false}; //两个map记录转换 map<string,int> mymap;map<int,string> mymap2;struct ans{string name;int count;};int compare(ans a1,ans a2){return a1.name<a2.name;}//求连通分量 void BFS(int count){vector<ans> res;//找root for(int i=0;i<count;i++){//找到一个root if(!visited[i]){//一个gang vector<int> v;int MAX = -1,index=-1,total = 0;;queue<int> q;q.push(i);visited[i]=true;while(!q.empty()){int t = q.front();q.pop();total += weight[t];v.push_back(t);if(MAX<weight[t]){MAX = weight[t];index = t;}for(int j=0;j<count;j++){if(!visited[j] && graph[t][j]==1){visited[j]=true;q.push(j);}}}//满足条件加进来 if(total>2*K && v.size()>2){ans a;a.name = mymap2[index];a.count = v.size();res.push_back(a);} }} cout<<res.size()<<endl;//排序啊 sort(res.begin(),res.end(),compare);for(int i=0;i<res.size();i++){cout<<res[i].name<<" "<<res[i].count<<endl;}}int main(int argc, char *argv[]) {int N,root=0,count=0;cin>>N>>K;//初始化graphfor(int i=0;i<MAX;i++){weight[i]=0;visited[i]=false;for(int j=0;j<MAX;j++){graph[i][j]=0;}} //输入 for(int i=0;i<N;i++){string name,name2;int w;cin>>name>>name2>>w;if(mymap.count(name)==0){mymap[name] = count;mymap2[count] =name;count++;}if(mymap.count(name2)==0){mymap[name2]=count;mymap2[count++]=name2;}int id = mymap[name],id2 = mymap[name2];graph[id][id2]=1;weight[id]+=w;weight[id2]+=w;graph[id2][id]=1;}//调用BFS //cout<<"count "<<count<<endl;BFS(count); return 0;}
