题目地址:https://pintia.cn/problem-sets/994805342720868352/problems/994805456881434624
题目解释:
给出若干人之间的通话长度(无向图),这些通话将他们分为若干组。每个组的总边权为该组内的所有的通话长度之和,而每个人的点权设为该人参与的通话长度之和。现在给定一个阈值K,且只要一个组的总边权超过K,并满足组内成员数超过2,则将该组视为“犯罪团伙Gang”,而该组内点权最大的人视为头目。要求输出“犯罪团伙”的个数,并按照头目姓名的字典序从小到大的顺序输出每个“犯罪团伙”的头目姓名和成员人数。
解题思路:
1.由于通话记录最多有1000条,那么最多有2000人,数组的大小要设为2000+。
2.巧妙使用map,实现姓名和该人的序号的对应。且对于map<type1,type2>是自动按照type1从小到大进行排序的,符合题目要求的按照字典序从小到达输出的要求。
可能会用到的map的函数有.size() .find(type) .begin() .end()等
3.采用dfs遍历,注意遍历的时候不要出现回退的情况。所以在遇到下一个可以到达的点的时候,先累加边权,再将该条边的边权置0,变成不可再走的边。
ac代码:
#include <iostream>
#include <string>
#include <map>
#define maxn 2020
#define INF 10000000000
using namespace std;
int G[maxn][maxn]={0},weight[maxn]={0};//邻接矩阵存边权,点权
int n,k,w,numperson=0;
bool vis[maxn]={false};
map<string,int> Stringtoint;//姓名->序号
map<int,string> intTostring;//序号->姓名
map<string,int> Gang;//最后输出,字典序从小到大
void DFS(int nowvis,int &head,int &numMeber,int &totalvalue)//遍历过程中不断更新head,numMeber和totalvalue
{
numMeber++;//成员数+1
vis[nowvis]=true;
if(weight[nowvis]>weight[head])
head=nowvis;
for(int i=0;i<numperson;i++)
{
if(G[nowvis][i]>0)//可访问
{
totalvalue+=G[nowvis][i];
G[nowvis][i]=G[i][nowvis]=0;//删除该条边,防止回头
if(!vis[i])
DFS(i,head,numMeber,totalvalue);
}
}
}
void DFSTrave()
{
for(int i=0;i<numperson;i++)
{
if(!vis[i])
{
int head=i,numMeber=0,totalvalue=0;
DFS(i,head,numMeber,totalvalue);
if(numMeber>2 && totalvalue>k)
Gang[intTostring[head]]=numMeber;
}
}
}
int change(string str)
{
if(Stringtoint.find(str)!=Stringtoint.end())
return Stringtoint[str];
else
{
Stringtoint[str]=numperson;
intTostring[numperson]=str;
return numperson++;
}
}
int main()
{
cin>>n>>k;
string str1,str2;
for(int i=0;i<n;i++)
{
cin >> str1 >> str2 >> w;
int di1 = change(str1);//di为序号
int di2 = change(str2);
weight[di1] += w;
weight[di2] += w;
G[di1][di2] += w;
G[di2][di1] += w;//无向图的边权
}
DFSTrave();
cout<<Gang.size()<<endl;
map<string,int>::iterator it;
for(it=Gang.begin();it!=Gang.end();it++)
cout<<it->first<<" "<<it->second<<endl;
return 0;
}