一、原题链接
题目详情 - 1034 Head of a Gang (30 分) (pintia.cn)
二、题面
One way that the police finds the head of a gang is to check people’s phone calls. If there is a phone call between A and B, we say that A and B is related. The weight of a relation is defined to be the total time length of all the phone calls made between the two persons. A “Gang” is a cluster of more than 2 persons who are related to each other with total relation weight being greater than a given threshold K. In each gang, the one with maximum total weight is the head. Now given a list of phone calls, you are supposed to find the gangs and the heads.
三、输入
Each input file contains one test case. For each case, the first line contains two positive numbers N and K (both less than or equal to 1000), the number of phone calls and the weight threthold, respectively. Then N lines follow, each in the following format:
Name1 Name2 Time
where Name1 and Name2 are the names of people at the two ends of the call, and Time is the length of the call. A name is a string of three capital letters chosen from A-Z. A time length is a positive integer which is no more than 1000 minutes.
四、输出
For each test case, first print in a line the total number of gangs. Then for each gang, print in a line the name of the head and the total number of the members. It is guaranteed that the head is unique for each gang. The output must be sorted according to the alphabetical order of the names of the heads.
五、思路
(看了半天没搞出什么名堂,翻了翻柳神的笔记)
1. 字符串与数值的转换(模块化的代码)
2. 求总的集合个数:考虑dfs
3. 求最大权重点:考虑dfs,关键是如何确定哪些点是一个集合的
4. 关于结果的字母序:单独拎出来排列
---------------------
说下一个柳神代码中几个比较妙的地方:
1. 使用地址符传入参数(个人平常用惯了全局变量,这样确实不好)
2. 关于两个weight的处理,某人的weight用数组存储,队伍的weight作为dfs的参数使用
3. 队伍中的最大位次直接进行比较(dfs参数head)
4. 通过map记录答案:
* 答案有两个数
* 字母序
* 去重(因为是逐个遍历下来的)
5. 如何保证每个路径(不是节点,节点已经用visit标记了):与节点不同,直接将路径置零即可(这个是我完全没注意到的细节)
其它帖子的思路还有并查集,即在做合并的时候进来将联系时间长的用户放在后面
六、code
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <map>
#define INF 0x3f3f3f3f
using namespace std;
const int N=2e3+5;
//特点:对于字符串的转化涉及到字母序,建议统一输入再处理
//strcmp(a,b):a<b,返回负数;a=b,返回0;a>b,返回正数
int G[N][N],weight[N];
map<int,string> iToS;
map<string,int> sToI;
map<string,int> ansMap; //结果用一个map存储,因为输出有两个数据,其中string不重复,而map对字符串自动排序,同时还可以去重
int num=0,n,m; //num是语义化的表达,只能从0开始,不能从1
int nameToNum(string name){
int ans;
if(sToI.find(name)==sToI.end()){
sToI[name]=num;
iToS[num]=name;
ans=num;
num++;
}else{
ans=sToI[name];
}
//cout << "num:" << ans << endl;
return ans;
}
int visit[N];
void dfs(int now,int &totalNum,int &totalWeight,int &head){ //head妙啊
//cout << "now:" << now << endl;
//cout << "totalWeight:" << totalWeight << endl;
//调整数据
visit[now]=1;
totalNum++;
//cout << "totalNum:" << totalNum << " totalWeight:" << totalWeight << endl;
if(weight[now]>weight[head]){
head=now;
}
for(int j=0;j<num;j++){
if(G[now][j]!=0){
totalWeight+=G[now][j];
G[now][j]=0;
G[j][now]=0;
if(visit[j]==0){
dfs(j,totalNum,totalWeight,head);
}
}
}
}
void dfsTravel(){
for(int i=0;i<num;i++){
memset(visit,0,sizeof(visit));
int totalWeight=0,totalNum=0,head=i;
dfs(i,totalNum,totalWeight,head);
//cout << "i:" << i << " totalNum:" << totalNum << " totalWeight:" << totalWeight << " head:" << head << endl;
if(totalNum>2&&totalWeight>m){
ansMap[iToS[head]]=totalNum;
}
}
}
int main(){
cin >> n >> m;
string a,b;
int value;
for(int i=0;i<n;i++){
cin >> a >> b >> value;
int numA=nameToNum(a),numB=nameToNum(b);
weight[numA]+=value;
weight[numB]+=value;
//无向图
G[numA][numB]+=value; //注意这里看你有重复
G[numB][numA]+=value;
}
dfsTravel();
cout << ansMap.size() << endl;
for(auto iterator=ansMap.begin();iterator!=ansMap.end();iterator++){
cout << iterator->first << " " << iterator->second << endl;
}
return 0;
}