[编程题]Head of a Gang
- 热度指数：5608 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 64M，其他语言128M
- 算法知识视频讲解
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 threthold 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.
输入描述:
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
输入
8 59 AAA BBB 10 BBB AAA 20 AAA CCC 40 DDD EEE 5 EEE DDD 70 FFF GGG 30 GGG HHH 20 HHH FFF 10 8 70 AAA BBB 10 BBB AAA 20 AAA CCC 40 DDD EEE 5 EEE DDD 70 FFF GGG 30 GGG HHH 20 HHH FFF 10
输出
2 AAA 3 GGG 3 0
使用并查集。建立了两个结构体，一个person用于保存每个人的名字、权重、所在集合的根节点下标。一个gang用于保存结果，每个帮派的头目及帮派的成员。之所欲需要第二个结果结构体是因为我在并查集的过程中无法保证根节点为头目，输出时没办法按名字升序输出，所以用一个结果结构体数组sort一下再输入。在建立一个sum数组保存每个集合的总权重，用于与k比较。下面是代码和注释：
#include<stdio.h>
#include<string.h>
#include<algorithm>
#define N 26
using namespace std;
typedef struct Person{
char name[5];
int weight;
int parents;//parents保存集合的根节点下标，根节点的parent保存集合成员个数
}Person;
typedef struct gang{
char head[5];
int number;
}gang;//结果结构体保存头目和帮派人数
Person p[N];
int sum[N];
bool cmp(gang a,gang b){
return strcmp(a.head,b.head)<0;
}//字典排序函数
int FindRoot(int x){
if(p[x].parents<0) return x;//parents小于0代表是根节点，且数值为成员个数
else{
p[x].parents=FindRoot(p[x].parents);
return p[x].parents;
}
}//并查集函数
int main(){
int n,k;
while(scanf("%d%d",&n,&k)!=EOF){
getchar();//用于消除缓冲区回车防止字符串输入出错
int i;
for(i=0;i<N;i++){
p[i].parents=-1;
p[i].weight=0;
sum[i]=0;
}//初始化
while(n--){
char name1[5],name2[5];
int weight,no1,no2,p1,p2;
scanf("%s%s%d",name1,name2,&weight);
getchar();//用于消除缓冲区同上
no1=name1[0]-'A';
no2=name2[0]-'A';//由名字找到这个人下标
strcpy(p[no1].name,name1);//记得要保存该人的名字
p[no1].weight+=weight;//每遇到这个人就要加上一次权重
strcpy(p[no2].name,name2);
p[no2].weight+=weight;
p1=FindRoot(no1);
p2=FindRoot(no2);
if(p1!=p2){//不是同一个集合要合并
p[p1].parents+=p[p2].parents;
p[p2].parents=p1;
sum[p1]=sum[p1]+sum[p2]+weight;
}//合并的过程，顺便加上集合的总权重
else
sum[p1]+=weight;//如果是同一个集合也要加上权重
}
int ans=0;//保存帮派数目
gang g[10];//结果数组，26个人帮派最多有8个，10的数组够了
for(i=0;i<N;i++){
if(p[i].parents<-2&&sum[i]>k){//人数超过2人，总权重大于k则为帮派
g[ans].number=-p[i].parents;//保存下帮派人数
int parent=i;//根节点存一下，其实有点多余，可以直接用i
int max=i;//权重最大者下标，初始为根节点
for(int j=0;j<N;j++){
if(FindRoot(j)==parent&&p[j].weight>p[max].weight)
max=j;//如果属于此集合且权重更大，替换一下
}
strcpy(g[ans].head,p[max].name);//把头目名字存进来
ans++;//接着存下一个帮派
}
}
printf("%d\n",ans);//输入帮派数目
sort(g,g+ans,cmp);//按字典sort一下
for(i=0;i<ans;i++)
printf("%s %d\n",g[i].head,g[i].number);//输出头目名字和帮派人数
}
return 0;//over，哈哈
}
编辑于 2018-01-20 21:08:57
回复(3)
思路：使用了并查集，每个人都有自身的通信量以及自己的父级(与本人有关联且个人通信量大于等于我的)，只有最上层的根的总通信量和人数是有效的，find函数主要是寻根，并且在过程中压缩路径。Union函数用于合并两个元素，其中的参数t是本次合并双方的通信量，用于加在双方的根的total通信量中，首先先寻找双方的根，若根不同的话，则进行相应的合并（个人通信量小的并入通信量大的）即修改father，并将原根的num_people、total复制过来，并将本次的通信量增加到本帮会的总通信量中，表明我是老大了，查到了我身上我就能给出这些数据。合并过程中，有可能本次合并的两个结点的个人通信量比根的个人通信量大，这时候就要换老大了。若寻双方的根后发现是在同一个帮会，这时候只需将本次的通信量加入老大维护的帮会总通信量total，并检查是否需要换老大，即这次合并的两个节点中是否有比根的通信量大的。
之后就是遍历map了，找出每个帮派的老大，检查人数够不够多，总通信量是否有威胁。
#include<iostream>
#include<string>
#include<map>
#include<vector>
#include<algorithm>
using namespace std;
struct E{
string father;
int num_people;
int self;
int total;
};
map<string, E>m;
string find(string root){
string son = root;
while (m[root].father != root)
root = m[root].father;
while (son != root){
string tmp = m[son].father;
m[son].father = root;
son = tmp;
}
return root;
}
void Union(string x, string y,int t){
string a = find(x);
string b = find(y);
if (a != b){
string i = (m[a].self >= m[b].self) ? a : b;
string j = (m[a].self >= m[b].self) ? b : a;
m[j].father = i;
m[i].num_people += m[j].num_people;
m[i].total += m[j].total;
m[i].total += t;
string larger = m[x].self > m[y].self ? x : y;
if (m[i].self < m[larger].self){
m[i].father = larger;
m[larger].father = larger;
m[larger].num_people = m[i].num_people;
m[larger].total = m[i].total;
}
}
else{
m[a].total += t;
string larger = m[x].self > m[y].self ? x : y;
if (m[a].self < m[larger].self){
m[a].father = larger;
m[larger].father = larger;
m[larger].num_people = m[a].num_people;
m[larger].total = m[a].total;
}
}
}
int main(){
int n, k;
while (scanf("%d%d", &n, &k) != EOF){
m.clear();
while (n--){
string s1, s2;
int t;
cin >> s1 >> s2 >> t;
//总通信量合并时再加到根
if (m.find(s1) == m.end()){
E tmp;
tmp.father = s1;
tmp.num_people = 1;
tmp.self = t;
tmp.total = 0;
m[s1] = tmp;
}
else
m[s1].self += t;
if (m.find(s2) == m.end()){
E tmp;
tmp.father = s2;
tmp.num_people = 1;
tmp.self = t;
tmp.total = 0;
m[s2] = tmp;
}
else
m[s2].self += t;
Union(s1, s2,t);
}
int res = 0;
vector<string>head;
for (map<string, E>::iterator it = m.begin(); it != m.end(); ++it){
if (it->second.father == it->first && it->second.total > k && it->second.num_people > 2){
head.push_back(it->first);
++res;
}
}
sort(head.begin(), head.end());
cout << res << endl;
for (int i = 0; i < head.size(); i++)
cout << head[i] << " " << m[head[i]].num_people << endl;
}
return 0;
}
#include<string>
#include<map>
#include<vector>
#include<algorithm>
using namespace std;
struct E{
string father;
int num_people;
int self;
int total;
};
map<string, E>m;
string find(string root){
string son = root;
while (m[root].father != root)
root = m[root].father;
while (son != root){
string tmp = m[son].father;
m[son].father = root;
son = tmp;
}
return root;
}
void Union(string x, string y,int t){
string a = find(x);
string b = find(y);
if (a != b){
string i = (m[a].self >= m[b].self) ? a : b;
string j = (m[a].self >= m[b].self) ? b : a;
m[j].father = i;
m[i].num_people += m[j].num_people;
m[i].total += m[j].total;
m[i].total += t;
string larger = m[x].self > m[y].self ? x : y;
if (m[i].self < m[larger].self){
m[i].father = larger;
m[larger].father = larger;
m[larger].num_people = m[i].num_people;
m[larger].total = m[i].total;
}
}
else{
m[a].total += t;
string larger = m[x].self > m[y].self ? x : y;
if (m[a].self < m[larger].self){
m[a].father = larger;
m[larger].father = larger;
m[larger].num_people = m[a].num_people;
m[larger].total = m[a].total;
}
}
}
int main(){
int n, k;
while (scanf("%d%d", &n, &k) != EOF){
m.clear();
while (n--){
string s1, s2;
int t;
cin >> s1 >> s2 >> t;
//总通信量合并时再加到根
if (m.find(s1) == m.end()){
E tmp;
tmp.father = s1;
tmp.num_people = 1;
tmp.self = t;
tmp.total = 0;
m[s1] = tmp;
}
else
m[s1].self += t;
if (m.find(s2) == m.end()){
E tmp;
tmp.father = s2;
tmp.num_people = 1;
tmp.self = t;
tmp.total = 0;
m[s2] = tmp;
}
else
m[s2].self += t;
Union(s1, s2,t);
}
int res = 0;
vector<string>head;
for (map<string, E>::iterator it = m.begin(); it != m.end(); ++it){
if (it->second.father == it->first && it->second.total > k && it->second.num_people > 2){
head.push_back(it->first);
++res;
}
}
sort(head.begin(), head.end());
cout << res << endl;
for (int i = 0; i < head.size(); i++)
cout << head[i] << " " << m[head[i]].num_people << endl;
}
return 0;
}
编辑于 2020-03-06 12:31:48
回复(0)
好坑啊，主要是题目理解了好几遍都理解错了。
在代码里详细写了注释，中途检测的话把中间注释掉的代码取消注释就行了。
我只用的map，结果创建了7个map... 我觉得用结构体的话应该能优化许多。
需要注意的地方是：
1. 系统输入有问题，它输入的是单个字母作为一个人。所以代码里应该用空格划分
2. 输入的k是帮派总权重的阈值，我一开始理解错了理解成了帮派头目的权重大于k才行。其实应该是帮派总权重大于k
3. 我一开始是用一个临时头目来存储整个帮派的人数和总权重（所以只有临时头目对应的人数和总权重是真的，其他的都是假的）。然后等输入结束后再把这个头目更新。
#include <iostream>
#include <cstdio>
#include <map>
#include <cstring>
#include <algorithm>
using namespace std;
map<string, string> up; //(个人, 临时头目)
map<string, int>weight; //(个人, 个人权重)
map<string, int>cluster; //(个人, 本帮派人数) 仅有临时头目对应的是真实的
map<string, int>clusterweight; //(临时头目, 帮派权重)
map<string, int>chosen; //(临时头目, 人数)
map<string, string>newHeader; //(临时头目, 最终头目)
map<string, int>chosen2;//(最终头目, 人数)
//找到临时头目
string Find(string x){
if(up.find(x)== up.end())
up[x]= x;
if(up[x]!=x){
up[x] = Find(up[x]);//路径压缩
}
return up[x];
}
//这个合并的结果，每个帮派的根可能并不是权重最大的
void Union(string x, string y, int num){
string fx = Find(x);
string fy = Find(y);
if(fx!=fy){ //来自不同的帮派
if(weight[fx]<weight[fy]){
up[fx]=fy; //头目归属
//帮派人数、总权重合并
cluster[fy]+=cluster[fx];
clusterweight[fy]+=clusterweight[fx];
clusterweight[fy]+=num;
}
else{
up[fy]=fx;
cluster[fx]+=cluster[fy];
clusterweight[fx]+=clusterweight[fy];
clusterweight[fx]+=num;
}
}
else{
//同一个帮派只要增加总权重
clusterweight[fx]+=num;
}
}
int main(){
int n,k;
while(cin>>n>>k){
//初始化
up.clear();
weight.clear();
cluster.clear();
chosen.clear();
newHeader.clear();
chosen2.clear();
clusterweight.clear();
getchar(); //结尾的换行符
string str;
string x, y, num;
for(int i=0; i<n;i++){
getline(cin, str, '\n');
int pos = str.find(' '); //第一个空格
x = str.substr(0,pos);
int pos2 = str.rfind(' '); //反向查找第一个空格
y = str.substr(pos+1, pos2-pos-1);
num = str.substr(pos2+1);
weight[x]+=std::stoi(num); //string 转int
weight[y]+=std::stoi(num);
//如果是新来的，先初始化一下cluster
if(cluster[x]==0) cluster[x]=1;
if(cluster[y]==0) cluster[y]=1;
Union(x,y,std::stoi(num));
}
map<string, string>::iterator it;
//把所有的都压缩一遍
for(it=up.begin(); it!=up.end(); it++){
Find(it->first);
}
// for(it=up.begin(); it!=up.end(); it++) {
// cout<<it->first<<" "<<it->second<<" "<<weight[it->first]<<" "<<cluster[it->second]<<clusterweight[it->second]<<endl;
// }
//到这一步，帮派已经划分完毕，先筛选人数和权重上符合条件的帮派，并把头目放到chosen里
map<string, int>::iterator it2;
for(it=up.begin(); it!=up.end(); it++){
if(it->second == it->first && cluster[it->first] >2 && clusterweight[it->first] >k){//“头目”
chosen[it->first] = cluster[it->first];
}
}
// for(it2=chosen.begin(); it2!=chosen.end(); it2++){
// cout<<it2->first<<" "<<it2->second<<" "<<weight[it2->first]<<endl;
// }
//更新头目，放到chosen2里
for(it2=chosen.begin(); it2!=chosen.end(); it2++){
string tempheader = it2->first;
int clusternum = it2->second;
newHeader[tempheader]=tempheader; //初始化最终头目是临时头目
//对于所有头目为临时头目的成员，选取个人权重最大的当作最终头目
for(it=up.begin(); it!=up.end(); it++) {
if (it->second == tempheader) {
if (weight[it->first] > weight[newHeader[tempheader]]) {
newHeader[tempheader] = it->first;
}
}
}
chosen2.insert(pair<string, int>(newHeader[tempheader], clusternum));
}
// map<string, int>::iterator itt;
// for(itt=chosen2.begin(); itt!=chosen2.end(); itt++){
// cout<<itt->first<<" "<<itt->second<<endl;
// }
//输出
cout<<chosen2.size()<<endl;
map<string, int>::iterator itt;
for(itt=chosen2.begin(); itt!=chosen2.end(); itt++){
cout<<itt->first<<" "<<itt->second<<endl;
}
}
return 0;
}
编辑于 2020-04-07 00:05:23
回复(0)
using namespace std;
#include <iostream>
#include <cstdio>
#include <cstring>
#include <map>
#include <vector>
map<string, int> M, Rank, size, sum;
map<string, string> par, head;
string find(string n){
if(n == par[n])return n;
else return find(par[n]);
}
void unite(string x, string y){
x = find(x);
y = find(y);
if(x == y)return;
if(Rank[x] <= Rank[y])par[x] = y;
else par[y] = x;
if(Rank[x] == Rank[y])++Rank[x];
}
int main(){
int n, k;
while(scanf("%d%d", &n, &k) != EOF){
M.clear(), Rank.clear(), head.clear(), size.clear(), sum.clear(), par.clear();
string a, b;
int v;
while(n--){
getchar();
cin>>a>>b>>v;
if(M.find(a) == M.end())M[a] = v;
else M[a] += v;
if(M.find(b) == M.end())M[b] = v;
else M[b] += v;
if(par.find(a) == par.end()){
par[a] = a;
Rank[a] = 1;
}
if(par.find(b) == par.end()){
par[b] = b;
Rank[b] = 1;
}
unite(a, b);
}
map<string, string>::iterator it;
for(it = par.begin();it!=par.end();++it){
string t = find(it->first);
if(head.find(t) == head.end()){
head[t] = it->first;
sum[t] = M[it->first];
size[t] = 1;
}
else{
if(M[it->first] > M[head[t]])head[t] = it->first;
sum[t] += M[it->first];
++size[t];
}
}
map<string, string>::iterator tt;
vector<string>ans;
for(tt = head.begin();tt!=head.end();++tt){
if(size[tt->first] > 2 and ((sum[tt->first] / 2) > k))ans.push_back(tt->first);
}
int s = ans.empty()?0:ans.size();
printf("%d\n", s);
for(int i(0);i<s;++i){
printf("%s %d\n", head[ans[i]].c_str(), size[ans[i]]);
}
}
return 0;
} 写个垃圾题解
发表于 2021-07-17 16:55:04
回复(0)
#include<iostream>
#include<cstring>
#include<map>
#include<algorithm>
using namespace std;
typedef struct GangInfo
{
string head_name;
int total_num,total_w;
}GangInfo;
map<string,string> name_map;
map<string,int> weight_map;
map<string,GangInfo> head_map;
bool Compare(GangInfo a,GangInfo b)
{
return a.head_name < b.head_name;
}
string FindRoot(string name)
{
if(!name_map.count(name))
{
return name;
}
else
{
string res = FindRoot(name_map[name]);
name_map[name] = res;
return res;
}
}
int main()
{
int N,K;
while(cin >> N >> K)
{
name_map.clear();
weight_map.clear();
head_map.clear();
string r1,r2,n1,n2;
int w;
while(N--)
{
cin >> n1 >> n2 >> w;
weight_map[n1] += w;
weight_map[n2] += w;
r1 = FindRoot(n1);
r2 = FindRoot(n2);
if(!head_map.count(r1))
{
head_map[r1].head_name = r1;
head_map[r1].total_num = 1;
head_map[r1].total_w = 0;
}
if(!head_map.count(r2))
{
head_map[r2].head_name = r2;
head_map[r2].total_num = 1;
head_map[r2].total_w = 0;
}
if(r1 != r2)
{
head_map[r1].total_num += head_map[r2].total_num;
head_map[r1].total_w += head_map[r2].total_w + w;
if(weight_map[head_map[r1].head_name] < weight_map[head_map[r2].head_name])
{
head_map[r1].head_name = head_map[r2].head_name;
}
if(weight_map[head_map[r1].head_name] < weight_map[n1]) head_map[r1].head_name = n1;
if(weight_map[head_map[r1].head_name] < weight_map[n2]) head_map[r1].head_name = n2;
name_map[r2] = r1;
head_map.erase(r2);
}
else
{
head_map[r1].total_w += w;
if(weight_map[head_map[r1].head_name] < weight_map[n1]) head_map[r1].head_name = n1;
if(weight_map[head_map[r1].head_name] < weight_map[n2]) head_map[r1].head_name = n2;
}
}
int count = 0;
GangInfo gn[30];
for(auto m : head_map)
{
if(m.second.total_num > 2 && m.second.total_w > K)
gn[count++] = m.second;
}
sort(gn,gn + count,Compare);
cout << count << endl;
for(int i = 0;i < count;i++)
{
cout << gn[i].head_name << " " << gn[i].total_num << endl;
}
}
return 0;
}
发表于 2021-02-05 14:22:34
回复(0)
#include<iostream>
#include<string>
#include<map>
#include<vector>
#include<algorithm>
using namespace std;
struct Node
{
string father;//他的根
int num_people;//他跟多少人打电话
int time;//此人累计打了多久电话
int gang_time;//以他为根的集合(团伙)打了多久电话
Node() {}
Node(string f, int n, int ti,int tt)
:father(f), num_people(n), time(ti), gang_time(tt) {}
};
map<string, Node> m;
string find(string root) //找root所在集合的根，同时压缩路劲
{
string son = root, tmp;
while (m[root].father != root)//不断找根
root = m[root].father;
while (son != root) //路劲压缩，将寻根路劲上的节点一次性都直接指向集合根节点
{
tmp = m[son].father;
m[son].father = root;
son = tmp;
}
return root;
}
void Union(string a, string b, int t)
{
string larger = m[a].time > m[b].time ? a : b;
a = find(a);
b = find(b);
string more, less;
if (a != b)//不在同一个集合，合并且大的为根
{ //括号不能丢
m[a].time >= m[b].time ? (more = a, less = b) : (more = b, less = a);
m[less].father = more;//通话时间少的并入通话时间多的
m[more].num_people += m[less].num_people;
m[more].gang_time += m[less].gang_time + t;
}
else//在同一个集合，只要根累加时长
{
m[a].gang_time += t;
more = a;
}
if (m[more].time < m[larger].time)//可能某一次通话时长比此集合根时长长，将其置为根
{
m[more].father = larger;
m[larger].father = larger;
m[larger].num_people = m[more].num_people;
m[larger].gang_time = m[more].gang_time;
}
}
int main()
{
int n, k;
while (cin>>n>>k)
{
m.clear();
while (n--)
{
string s1, s2;
int time;
cin >> s1 >> s2 >> time;
//总通信量合并时再加到根
if (m.find(s1) == m.end())
{
Node tmp(s1,1,time,0);
m[s1] = tmp;
}
else
m[s1].time += time;
if (m.find(s2) == m.end())
{
Node tmp(s2, 1, time, 0);
m[s2] = tmp;
}
else
m[s2].time += time;
Union(s1, s2, time);//并入集合
}
int gangs = 0;//团伙数量
vector<string> head;
for (map<string, Node>::iterator it = m.begin(); it != m.end(); it++)
{ //是集合的根(老大)+超过威胁+团伙人数大于2
if (it->second.father == it->first
&& it->second.gang_time > k && it->second.num_people > 2)
{
head.push_back(it->first);
gangs++;
}
}
sort(head.begin(), head.end());
cout << gangs << endl;
for (int i = 0; i < head.size(); i++)
cout << head[i] << " " << m[head[i]].num_people << endl;
head.clear();
}
return 0;
} 并查集，参考 “香香爱上蔡文姬” 解答，略作修改
编辑于 2020-06-29 20:44:20
回复(0)
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1000;
struct person{
string name;
int weight;
int father;
int height;
int visit;
int n;//下标位置 仅对根节点有效 其实可以不用 因为根节点的father就是自己 所以不用n再来记录
};
struct gang
{
string boss;
int num;
gang(string name,int n):boss(name),num(n){}
};
person member[MAXN]; //成员数组
void init() //初始化函数
{
for(int i=0;i<MAXN;i++)
{
member[i].name="";
member[i].weight=0;
member[i].father=i;
member[i].visit=0;
member[i].height=0;
}
}
int find(int x) //查找树根函数
{
if(member[x].father!=x)
{
x=find(member[x].father);
member[x].father=x;
}
return x;
}
void Union(int x,int y,int w)
{
member[x].visit=1; //更新是否有
member[y].visit=1;
member[x].weight+=w; //更新权值
member[y].weight+=w;
x=find(x);
y=find(y);
if(x!=y)
{
if(member[x].height<member[y].height)
member[x].father=y;
else if(member[y].height<member[x].height)
member[y].father=x;
else
{
member[x].father=y;
member[y].height++;
}
}
}
int compare1(person x,person y)//帮派成员排序函数的比较 比权值
{
return x.weight>y.weight; //权值大的放在最前面
}
int compare2(gang x,gang y)//帮派按照大哥姓名 按字母表顺序排序
{
return x.boss<y.boss;
}
int main()
{
int n,k; //k代表的是门限
while(cin>>n>>k)
{
init();
for(int i=0;i<n;i++)//获取输入
{
string str1,str2;
int weight;
cin>>str1>>str2>>weight;
int x=str1[0]-'A';
int y=str2[0]-'A';
member[x].name=str1;
member[y].name=str2;
Union(x,y,weight);
}
vector<person> root;
//找出根节点的函数
for(int i=0;i<MAXN;i++)
{
if(member[i].visit&&(i==member[i].father))
{
// member[i].n=i;//结构体n成员仅对根节点有效 可以不用
root.push_back(member[i]);
}
}
vector<gang> party;//创建帮派向量
//根节点未必是boss 所以要找出所有根处于该根节点的节点 并排序 找出boss以及帮派成员数目
for(int i=0;i<root.size();i++)//遍历根节点 创建帮派
{
vector<person> myvector;
int w=0;//记录帮派总权值
for(int j=0;j<MAXN;j++)//找出该帮派所有成员
{
if(member[j].visit&&(find(j)==root[i].father))//确认过眼神
{//因为根节点的父亲就是自己 所以不需要再记录根节点的下标了
w+=member[j].weight;//帮派总权值增加
myvector.push_back(member[j]);//成员入队
}
}
if((w/2)>=k&&myvector.size()>2)//符合帮派条件
{
sort(myvector.begin(),myvector.end(),compare1);//重新整理
person b=myvector[0];//找出大哥
//建立帮派
gang current(b.name,myvector.size());//以大哥名字和人数建立帮派
party.push_back(current);//加入总帮派向量
}
}
//输出总帮派数
cout<<party.size()<<endl;
//将所有帮派按大哥姓名进行排序
sort(party.begin(),party.end(),compare2);
//输出帮派信息 大哥以及人数
for(int i=0;i<party.size();i++)
{
cout<<party[i].boss<<" "<<party[i].num<<endl;
}
}
return 0;
}
发表于 2020-04-21 12:30:50
回复(1)
利用并查集实现集合的合并和查询，根节点为团队的首脑，本题并未出现复杂的成员名字，所以可以根据首字母的顺序，将其与26个数组成员一一对应起来，最后遍历数组，即可实现排序输出。难点在于：根据权重更新一个团体的首脑。
#include <iostream>
#include <cstring>
using namespace std;
const int MAXN = 26; // A-Z共26个字母
struct Person { // 个人
char name[4];
int weight; // 权重
int father; // 父节点
int number; // 记录集合元素数量,即团体成员数目,只有根节点的该字段有意义
int weight_sum; // 记录关系权重总和,只有根节点的该字段有意义
};
struct Gang { // 帮派
char head[4]; // 首领
int number; // 成员
};
Person p[MAXN];
Gang g[MAXN];
void Initial () // 初始化
{
for (int i = 0; i < MAXN; i++) {
Person s = {"", 0, i, 1, 0};
p[i] = s;
Gang t = {"", 0};
g[i] = t;
}
}
int Find (int x) // 查找根节点
{
if (p[x].father != x) { // 根节点的父结点为自身
p[x].father = Find(p[x].father);
}
return p[x].father;
}
void Update (int x, int weight) // 更新集合
{
p[x].weight += weight;
while (p[x].weight > p[p[x].father].weight) {
int temp = p[x].father;
if (p[temp].father == temp) { // 若父节点是根节点,x成为新的根结点
p[x].father = x; // 指向父节点的指针需指向自己
p[x].number = p[temp].number; // x更新number
p[x].weight_sum = p[temp].weight_sum; // x更新weight_sum,此处weight_sum并未加上weight,因为若x,y两个结点在一个集合中,可能导致x,y轮换为根结点,加了两次weight
p[temp].father = x;
}
else { // 若父节点不是根节点,只需更新父子关系,number和weight_sum只在根节点有意义
p[x].father = p[temp].father;
p[temp].father = x;
}
}
}
void Union (int x, int y, int weight) // 合并集合
{
x = Find(x);
y = Find(y);
if (x != y) { // 若x,y所在集合不是同一个 ,权重大的根节点作为新的根节点
if (p[x].weight < p[y].weight) {
p[x].father = y;
p[y].number += p[x].number;
p[y].weight_sum += p[x].weight_sum + weight;
}
else if (p[x].weight > p[y].weight) {
p[y].father = x;
p[x].number += p[y].number;
p[x].weight_sum += p[y].weight_sum + weight;
}
else { // 若两个根节点权重相同,字典排序小的作为新的根节点
if (x < y) {
p[y].father = x;
p[x].number += p[y].number;
p[x].weight_sum += p[y].weight_sum + weight;
}
else {
p[x].father = y;
p[y].number += p[x].number;
p[y].weight_sum += p[x].weight_sum + weight;
}
}
}
else { // 若x,y在一个集合,只需根节点的weight_sum加上weight
p[x].weight_sum += weight;
}
}
int main ()
{
int N, K;
while (cin >> N >> K) {
char a[4], b[4];
int x, y, weight;
Initial(); // 初始化
for (int i = 0; i < N; i++) {
cin >> a >> b >> weight;
x = int (a[0] - 'A'); // 利用名字首字母在A-Z的顺序保存到数组相应位置,即可实现排序
y = int (b[0] - 'A');
strcpy(p[x].name, a);
strcpy(p[y].name, b);
Update(x, weight); // 先更新
Update(y, weight);
Union(x, y, weight); // 后合并
}
int gangNumber = 0;
for (int i = 0, j = 0; i < MAXN && j < MAXN; i++) {
if (p[i].father == i && p[i].number > 2 && p[i].weight_sum > K) { // 父节点为自身是成为一个团体的首脑的首要条件
strcpy(g[j].head, p[i].name);
g[j].number = p[i].number;
j++;
}
gangNumber = j;
}
if (gangNumber > 0) {
cout << gangNumber << endl;
for (int i = 0; i < gangNumber; i++) {
cout << g[i].head << ' ' << g[i].number << endl;
}
}
else {
cout << 0 << endl;
}
}
return 0;
}
编辑于 2020-04-08 19:15:37
回复(0)
#include <iostream>
#include <cstdio>
#include <map>
#include <algorithm>
#include <string>
using namespace std;
/*题目要求的是：
每个人都有一个通话的分钟，一个团伙人数要求两人以上，团伙的头目定义为通话最多的人
每个人的姓名为A-Z的26个字母。。。
*/
//认真写注释啦啦啦
//该结构体虽然名字叫Gang,但是用它来存的是连通子图中的数据
struct Gang{
char id; //该连通子图的父节点，注意，这并不是头目
int personNum; //该团伙人数
int weight; //团伙总的通信数量*2，因为是把每个人都算了两遍
char name; //头目的名字
int head; //这才是头目鸭
};
const int MAX_N = 26; //题目测评的人名全部为A-Z的字母
int father[MAX_N]; //并查集中各元素的父亲的概念
int height[MAX_N]; //并查集中的树的高度
bool visit[MAX_N]; //该名字是否出现
int weight[MAX_N]; //每个人通话分钟的权值
bool Compare(Gang x, Gang y){ //该函数用于对团伙进行名字为参数的排序，按名字从小到大
return x.name < y.name;
}
void Initial(){ //初始化函数
for(int i = 0; i < MAX_N; ++i){
father[i] = i;
height[i] = 0;
visit[i] = false;
weight[i] = 0;
}
return;
}
int Find(int x){ //并查集的查找函数
if(x != father[x]){
father[x] = Find(father[x]);
}
return father[x];
}
void Union(int x, int y){ //并查集的合并函数
x = Find(x);
y = Find(y);
if(x != y){
if(height[x] < height[y]){
father[x] = y;
}
else if(height[x] > height[y]){
father[y] = x;
}
else{
father[x] = y;
height[y]++;
}
}
return;
}
int main(){
int n, k; //n代表有n组联系, k表***胁值
//将成员分成组
while(cin >> n >> k){
getchar(); //一定注意吞掉回车，不然后面读入乱套！！！
Initial();
char c1, c2;
int w;
for(int i = 0; i < n; ++i){
scanf("%c %c %d", &c1, &c2, &w); //用scanf约定格式读，若用cin，中间空格可能会被读入
getchar(); //还是一样要吞掉回车，下一次还要读字符
int ia = c1 - 'A'; //索引鸭
int ib = c2 - 'A';
visit[ia] = true;
visit[ib] = true;
weight[ia] += w;
weight[ib] += w;
Union(ia, ib); //合并集合
}
int component = 0; //连通子图的个数
Gang gang[MAX_N]; //保存团伙的头目姓名以及人数
for(int i = 0; i < MAX_N; ++i){ //初始化
gang[i].personNum = 0;
gang[i].weight = 0;
}
//对连通子图，将其信息保存下：father（id）、头目【头目先保存为father，说不定就是它呢】（head）
//头目姓名（name）
for(int i = 0; i < MAX_N; ++i){
if(visit[i]){
if(father[i] == i){
gang[component].id = i;
gang[component].head = i;
gang[component].name = i + 'A';
component++;
}
}
}
//对于每个父亲，遍历找团伙中的成员，包括成员数量、同时查找过程更换头目
for(int i = 0; i < component; ++i){
int f = gang[i].id;
for(int j = 0; j < MAX_N; ++j){
if(!visit[j]){
continue;
}
if(f == Find(j)){
gang[i].personNum++; //团伙人数
gang[i].weight += weight[j]; //团伙的通话分钟
if(weight[j] > weight[gang[i].head]){
gang[i].name = j + 'A'; //更换头目姓名
gang[i].head = j;
}
}
}
}
//对团队根据名字进行排队
sort(gang, gang + component, Compare);
//输入条件符合的团伙
int answer = 0; //满足条件的团伙数量
for(int i = 0; i < component; ++i){
if(gang[i].personNum > 2 && gang[i].weight > 2 * k){
answer++;
}
}
cout << answer << endl;
//输出团伙的头目、人数
for(int i = 0; i < component; ++i){
if(gang[i].personNum > 2 && gang[i].weight > 2 * k){
cout << gang[i].name << " " << gang[i].personNum << endl;
}
}
}
return 0;
}
编辑于 2020-03-28 20:47:00
回复(1)
dfs遍历求解
#include<iostream>
(720)#include<map>
#include<set>
using namespace std;
const int maxn=2010,inf=1e8;
int G[maxn][maxn]= {0},w[maxn],pnum=0,n,k,allW,gangnum,headW,head;
bool vist[maxn]= {false};
map<string,int> mp,ans;
map<int,string> pm;
void dfs(int i) {
vist[i]=true;
gangnum++;
allW+=w[i];
if(headW<w[i]) {
head=i;
headW=w[i];
}
for(int j=1; j<=pnum; j++) {
if(G[i][j]!=0&&vist[j]==false) {
dfs(j);
}
}
}
int change(string s) {
if(mp.find(s)!=mp.end()) {
return mp[s];
} else {
mp[s]=++pnum;
pm[pnum]=s;
return pnum;
}
}
void dfstrave() {
for(int i=1; i<=pnum; i++) {
allW=gangnum=headW=0;
if(vist[i]==false) {
dfs(i);
if(gangnum>2&&allW/2>k) {
ans[pm[head]]=gangnum;
}
}
}
}
int main() {
scanf("%d %d",&n,&k);
string a,b;
for(int i=0,z; i<n; i++) {
cin>>a>>b;
scanf("%d",&z);
int id1=change(a),id2=change(b);
w[id1]+=z;
w[id2]+=z;
G[id1][id2]+=z;
G[id2][id1]+=z;
}
dfstrave();
printf("%d\n",ans.size());
if(ans.size()!=0) {
for(map<string,int>::iterator it=ans.begin(); it!=ans.end(); it++) {
printf("%s %d\n",it->first.c_str(),it->second);
}
}
}
发表于 2020-03-27 10:43:14
回复(0)
/*一道题从读题到最后AC花了10个小时，首先题目的样例就是个坑，人名给的三个重复字母，例如AAA，结果测评的例子都是单个字母的名字。
一开始提交总是提示数组越界，找了一万年。第二，读懂题意很关键，总体思想并查集计算连通分量，然后每个连通分量去判断符不符合题目的
要求，需要记录的东西有点多，没用结构体，因为最多26个字母，所有信息全开个26的数组就完事了，用了一个二维数组去记录，为了最后判断
"帮派"的定义，从0-25遍历自然结果就成了排序好的，我可真是个天才*/
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 26;
int father[MAXN];
int height[MAXN];
int weight[MAXN];
int arr[MAXN];
bool vis[MAXN];
void Init(){
for(int i = 0; i < MAXN; ++i){
father[i] = i;
height[i] = 0;
weight[i] = 0;
arr[i] = 0;
vis[i] = false;
}
return;
}
int Find(int x){
if(x != father[x]){
father[x] = Find(father[x]);
}
return father[x];
}
void Union(int x, int y){
x = Find(x);
y = Find(y);
if(x != y){
if(height[x] > height[y]){
father[y] = x;
}
else if(height[x] < height[y]){
father[x] = y;
}
else{
father[x] = y;
height[y]++;
}
}
return;
}
int main(){
int n, k;
while(cin >> n >> k){
getchar();
Init();
for(int i = 0; i < n; ++i){
string str;
getline(cin, str);
int a = str[0] - 'A';
int b = str[2] - 'A';
string s = str.substr(4);
int sum = 0;
for(int j = 0; j < s.size(); ++j){
sum *= 10;
sum += s[j] - '0';
}
weight[a] += sum;
weight[b] += sum;
Union(a, b);
vis[a] = true;
vis[b] = true;
}
int dou[MAXN][MAXN];
for(int i = 0; i < MAXN; ++i){
for(int j = 0; j < MAXN; ++j){
dou[i][j] = 0;
}
}
for(int i = 0; i < MAXN; ++i){
if(vis[i]){
if(Find(i) != i){
dou[Find(i)][i] = 1;
}
}
}
int val;
int cas = 0;
string head;
for(int i = 0; i < MAXN; ++i){ //从0到25，对应字典序'A'到'Z'
int num = 0;
int max = -1;
int su = weight[i];
for(int j = 0; j < MAXN; ++j){
if(dou[i][j] == 1){
num++;
su += weight[j];
if(max < weight[j]){
max = weight[j];
val = j;
}
}
}
if(max < weight[i]){
val = i;
}
if(num > 1 && (su / 2) > k){ //满足题目中所谓的帮派要求，su为权重总和的2倍，这个算算就知道了
head[cas] = char(val + 'A');
arr[cas] = num + 1;
cas++;
}
}
if(cas == 0){
cout << "0" << endl;
}
else{
cout << cas << endl;
for(int i = 0; i < cas; ++i){
cout << head[i] << " " << arr[i] << endl;
}
}
}
return 0;
}
发表于 2020-03-25 10:14:32
回复(0)
有大佬看一下为什么我过不了1000个数据的那个，大部分都可以通过
#include<iostream>
(720)#include<map>
#include<cstring>
using namespace std;
int bcj[26];
int Time[26];
string visit[26];
map<int,int> myMap;
int find(int x){
if(bcj[x]==x) return x;
else return find(bcj[x]);
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n,k;
while(cin>>n>>k){
for(int i=0;i<26;i++)
bcj[i]=i;
myMap.clear();
fill(visit,visit+26," ");
memset(Time,0,sizeof(Time));
string a,b;
int t,x,y,p,q;
for(int i=0;i<n;i++){
cin>>a>>b>>t;
x=a[0]-'A';
y=b[0]-'A';
visit[x]=a;
visit[y]=b;
Time[x]+=t;
Time[y]+=t;
p=find(x);
if(Time[x]>Time[p]){
bcj[p]=bcj[x]=x;
Time[x]=Time[p]+t;
p=x;
}
q=find(y);
if(Time[y]>Time[q]){
bcj[q]=bcj[y]=y;
Time[y]=Time[q]+t;
q=y;
}
if(Time[p]<Time[q]){
bcj[p]=q;
if(q!=x&&q!=y)
Time[q] += t;
}
else {
bcj[q]=p;
if(p!=x&&p!=y)
Time[p] += t;
}
}
for(int i=0;i<26;i++){
if(visit[i]!=" ") myMap[find(visit[i][0]-'A')]++;
}
int cou=0;
for(map<int,int>::iterator it=myMap.begin();it!=myMap.end();it++){
if(Time[it->first]>k&&it->second>2)
cou++;
}
cout<<cou<<endl;
for(map<int,int>::iterator it=myMap.begin();it!=myMap.end();it++){
if(Time[it->first]>k&&it->second>2)
cout<<visit[it->first]<<" "<<it->second<<endl;
}
}
return 0;
}
发表于 2020-03-24 13:29:39
回复(0)
构造图的邻接表，然后遍历。在模拟题的路上越走越黑。。。。
#include <bits/stdc++.h>
using namespace std;
// 用邻接表构造图
class Edge { // 边
public:
int weight; // 边权
string nodeName; // 边所连接的顶点名
Edge *next; // 下一条边
Edge() {
weight = 0;
next = nullptr;
}
Edge(int weight, string nodeName, Edge *next) {
this->weight = weight;
this->nodeName = std::move(nodeName);
this->next = next;
}
};
class GNode { // 顶点
public:
string nodeName; // 顶点名
Edge *head; // 边指针
GNode() {
head = nullptr;
}
GNode(string nodeName, Edge *head) {
this->nodeName = std::move(nodeName);
this->head = head;
}
};
map<string, GNode *> graph; // <string, GNode*> --> <顶点， 顶点指针>
map<string, bool> visit;
void InitialVisit() {
map<string, bool>::iterator it;
for (it = visit.begin(); it != visit.end(); it++) {
it->second = false;
}
}
// 插入 node1 -> node2 的边
void InsertEdge(const string &node1, const string &node2, int weight) {
if (graph.find(node1) != graph.end()) { // 如果这个顶点以及存在，则将边加入这个顶点 （GNode 的 Edge；Edge的链表使用头插法）
GNode *node = graph[node1];
Edge *head = node->head;
Edge *newEdge = new Edge(weight, node2, head);
node->head = newEdge;
graph[node1] = node;
} else { // 如果这个点不存在，则新建一个顶点， 然后将边加入；
Edge *edge = new Edge(weight, node2, nullptr);
auto *gNode = new GNode(node1, edge);
graph[node1] = gNode;
}
visit[node1] = false;
}
bool Sort(const pair<string, int> &p1, const pair<string, int> &p2) {
return p1.first < p2.first;
}
vector<map<string, int> *>* Solution() {
auto *vm = new vector<map<string, int> *>;
vm->clear();
for (auto &i : graph) {
stack<GNode *> S;
if (visit[i.first]) {
continue;
}
S.push(i.second);
auto *m = new map<string, int>;
m->clear();
while (!S.empty()) {
GNode *gNode = S.top();
S.pop();
Edge *edge = gNode->head;
// cout << " --- " << gNode->nodeName;
visit[gNode->nodeName] = true;
while (edge != nullptr) {
if (!visit[edge->nodeName]) {
S.push(graph[edge->nodeName]);
visit[edge->nodeName] = true;
}
(*m)[gNode->nodeName] += edge->weight;
(*m)[edge->nodeName] += edge->weight;
edge = edge->next;
}
}
if (!m->empty() && m->size() >= 3) vm->push_back(m);
}
return vm;
}
void showResult(vector<map<string, int> *> *vm, int threshold) {
vector<pair<string, int>> vp;
for (auto m : *vm) {
if (m->size() >= 3) {
int total = 0;
int maxWeight = INT_MIN;
string maxString;
for (auto &j : *m) {
if (j.second > maxWeight) {
maxWeight = j.second;
maxString = j.first;
}
total += j.second;
}
if (total > threshold * 4) {
// cout << maxString << " " << m->size() << endl;
vp.push_back(make_pair(maxString, m->size()));
}
}
}
if (!vp.empty()) {
sort(vp.begin(), vp.end(), Sort);
cout << vp.size() << endl;
for (const pair<string, int>& p : vp) {
cout << p.first << " " << p.second << endl;
}
} else {
cout << 0 << endl;
}
}
int main() {
int n, k;
while (cin >> n >> k) {
graph.clear();
string str1;
string str2;
int weight;
for (int i = 0; i < n; ++i) {
cin >> str1 >> str2 >> weight;
InsertEdge(str1, str2, weight);
InsertEdge(str2, str1, weight); //构造无向图 ，插入两条边
}
InitialVisit();
vector<map<string, int> *> *mp = Solution();
showResult(mp, k);
}
return 0;
}
发表于 2020-03-10 16:51:32
回复(0)
并查集判断连通分量（Cluster）个数，接着遍历连通分量，输出有效的帮会（gang）
#include <iostream>
#include <map>
#include <algorithm>
using namespace std;
#define MaxN 1000
typedef struct _Cluster
{
string head; int mem_cnt, total_wgt;
}Cluster;
map<string, int> degree; map<string, string> tree;
typedef struct _Ans
{
string head; int mem_cnt;
bool operator <(const _Ans& a) const { return head < a.head; }
}Ans;
string findroot(string name)
{
if (!tree.count(name)) return name;
tree[name] = findroot(tree[name]);
return tree[name];
}
int main()
{
int n = 0, k = 0; map<string, Cluster>::iterator iter;
string name1, name2; int wgt = 0; map<string, Cluster> gang; Ans ans[500]; int cnt = 0;
while (cin>>n>>k)
{
tree.clear(); gang.clear(); degree.clear(); cnt = 0;
while (n-- && cin >> name1 >> name2 >> wgt)
{
degree[name1] += wgt; degree[name2] += wgt;
string t1 = findroot(name1); string t2 = findroot(name2);
if (!gang.count(t1)) { gang[t1].head = t1; gang[t1].mem_cnt = 1; gang[t1].total_wgt = 0; }
if (!gang.count(t2)) { gang[t2].head = t2; gang[t2].mem_cnt = 1; gang[t2].total_wgt = 0; }
if (t2 != t1)
{
gang[t1].mem_cnt += gang[t2].mem_cnt; gang[t1].total_wgt = gang[t1].total_wgt + wgt + gang[t2].total_wgt;
if (degree[gang[t1].head] < degree[gang[t2].head]) gang[t1].head = gang[t2].head;
if (degree[gang[t1].head] < degree[name1]) gang[t1].head = name1;
if (degree[gang[t1].head] < degree[name2]) gang[t1].head = name2;
tree[t2] = t1; gang.erase(t2);
}
else
{
gang[t1].total_wgt += wgt;
if (degree[gang[t1].head] < degree[name1]) gang[t1].head = name1;
if (degree[gang[t1].head] < degree[name2]) gang[t1].head = name2;
}
}
for (iter = gang.begin(); iter != gang.end(); iter++)
{
if (iter->second.mem_cnt > 2 && iter->second.total_wgt > k) { ans[cnt].head = iter->second.head; ans[cnt].mem_cnt = iter->second.mem_cnt; ++cnt; }
}
sort(ans, ans + cnt); cout << cnt << endl;
for (int i = 0; i < cnt; ++i) cout << ans[i].head << ' ' << ans[i].mem_cnt << endl;
}
return 0;
}
发表于 2020-02-20 16:10:48
回复(0)
来个java版的。DFS遍历图，找出所有联通子图，然后子图的边权总和。
package com.liyc.algs.pata;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
/**
* 构建Map<index, name>, 构建图g[name1][name2]
* DFS遍历图，找出所有联通子图，然后子图的边权总和。
*/
public class A1034 {
// 图
private static int[][] g;
// 顶点是否已访问过
private static int[] v;
// 顶点权重
private static int[] w;
// 阀值
private static int threthold;
// 总人数
private static int personsN;
public static void main(String[] args) throws IOException {
BufferedReader bf=new BufferedReader(new InputStreamReader(System.in));
String line1 = bf.readLine();
String[] line1as = line1.split(" ");
int totalcalls = Integer.valueOf(line1as[0]);
threthold = Integer.valueOf(line1as[1]);
int maxpersons = totalcalls * 2;
int index = 0;
Map<Integer, String> persons = new HashMap<>(maxpersons);
g = new int[maxpersons][maxpersons];
v = new int[maxpersons];
w = new int[maxpersons];
// 构建图
for (int k = 0; k < totalcalls; k++) {
String[] lines = bf.readLine().split(" ");
String name1 = lines[0];
String name2 = lines[1];
int i = 0;
if(!persons.containsValue(name1)){
i = index++;
persons.put(i, name1);
} else{
i = getKeyFromValue(persons, name1);
}
int j = 0;
if(!persons.containsValue(name2)){
j = index++;
persons.put(j, name2);
} else{
j = getKeyFromValue(persons, name2);
}
int time = Integer.valueOf(lines[2]);
g[i][j] += time;
g[j][i] += time;
w[j] = w[j] + time;
w[i] = w[i] + time;
}
bf.close();
personsN = persons.size();
// 保存各个联通子图
Set<Set<Integer>> subg = new HashSet<>();
// 遍历图
for (int i = 0; i < personsN; i++) {
if( v[i] > 0){
continue;
}
Set<Integer> set = new HashSet<>(maxpersons);
subg.add(set);
dfs(i, set);
}
int count = 0;
Map<Integer, Integer> ps = new TreeMap<>(Comparator.comparing(persons::get));
// 遍历各子图判断，存入ps
for (Set<Integer> set : subg){
if(set.size() <= 2){
continue;
}
int max = -1;
int sum = 0;
for (int i : set) {
int iw = w[i];
sum += iw;
if (max == -1 || iw > w[max]) {
max = i;
}
}
if( sum /2 <= threthold) {
continue;
}
count++;
ps.put(max, set.size());
}
System.out.println(count);
if(count==0){
return;
}
ps.forEach((k, v)->{
String name = persons.get(k);
System.out.println(name+" "+ps.get(k));
});
}
private static int getKeyFromValue(Map<Integer, String> persons, String name1) {
Set<Map.Entry<Integer, String>> set = persons.entrySet();
for (Map.Entry<Integer, String> en : set) {
if(en.getValue().equals(name1)) {
return en.getKey();
}
}
return 0;
}
private static void dfs(int i, Set<Integer> list) {
v[i] = 1;
list.add(i);
for (int j = 0; j < personsN; j++) {
if(g[i][j] == 0){
continue;
}
if(v[j] > 0) {
continue;
}
dfs(j, list);
}
}
}
发表于 2019-10-18 16:56:40
回复(0)
//并查集思想
//在读入数据的时候，就把人名转化成0，1，2，初始化并查集。并查集中设置了三个变量，
//父节点、该点的权重和如果作为领袖的话，本帮的所有权重值。
//在读入数据的时候就更新每个人的权重。
//然后就是常规并查集思想，判断两个边是不是在同一个集合中，不是的话，进行合并。
//合并的时候选权值大的作为父节点，因为这样直接就是头领。同时需要遍历他的子节点
//是不是另一些节点的父节点。同时在领袖的节点中记录整个帮派的权值，以便和k比较
//然后遍历并查集，寻找头节点，并记录该帮有多少人，符合要求的压入vector中
//最后vector按照字典序升序sort输出。
#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
#include <queue>
#include <math.h>
#include <cmath>
#include <string>
#include <sstream>
#include <set>
#define INF 0x3f3f3f3f
#pragma warning(disable:4996)
using namespace std;
typedef struct {
int x, y, w;
}edge;
typedef struct{
int father;
int weight;
int total;
}node;
typedef struct {
string s;
int num;
}ans;
vector<node> juSet;
int getIndex(vector<string> &name,string temp){
int i = 0 ;
for (i = 0; i < name.size();i++) {
if (name[i] == temp)
return i;
}
name.push_back(temp);
return i;
}
void addJuSet(int x,int weight) {
if (x >= juSet.size()) {
node temp;
temp.father = x;
temp.weight = weight;
temp.total = 0;
juSet.push_back(temp);
return;
}
else {
juSet[x].weight += weight;
return;
}
}
bool cmp(ans a, ans b) {
return a.s < b.s;
}
int findSet(int x) {
while (x != juSet[x].father) {
x = juSet[x].father;
}
return x;
}
void Union(int x, int y , int weight) {
if (x == y)
return;
if (juSet[x].weight > juSet[y].weight) {
juSet[y].father = x;
juSet[x].total += weight;
//所有以y为父节点的都应该指向x，且y的total也应该给x。
for (int i = 0; i < juSet.size();i++) {
if (juSet[i].father == y) {
juSet[i].father = x;
juSet[x].total += juSet[i].total;
}
}
}
else {
juSet[x].father = y;
juSet[y].total += weight;
for (int i = 0; i < juSet.size();i++) {
if (juSet[i].father == x) {
juSet[i].father = y;
juSet[y].total += juSet[i].total;
}
}
}
}
void addWeight(int x, int weight) {
juSet[x].total += weight;
}
int main()
{
int n, k;
while (scanf("%d%d", &n, &k) != EOF) {
vector<string> name;
vector<edge> edgeSet;
string temp1, temp2;
edge tempEdge;
node tempNode;
int weight;
int x, y;
for (int i = 0; i < n; i++) {
cin >> temp1 >> temp2 >> weight;
x = getIndex(name,temp1);
addJuSet(x, weight);
y = getIndex(name,temp2);
addJuSet(y, weight);
tempEdge.x = x; tempEdge.y = y; tempEdge.w = weight;
edgeSet.push_back(tempEdge);
}
int fatherX, fatherY;
for (int i = 0; i < edgeSet.size();i++) {
fatherX = findSet(edgeSet[i].x);
fatherY = findSet(edgeSet[i].y);
if (fatherX != fatherY) {
Union(fatherX, fatherY,edgeSet[i].w);
}
else {
addWeight(fatherX, edgeSet[i].w);
}
}
ans tempAns;
vector<ans> result;
for (int i = 0; i < juSet.size();i++) {
if (juSet[i].father == i && juSet[i].total>k) {
int count = 0;
for (int j = 0; j < juSet.size();j++) {
if (juSet[j].father == i)
count++;
}
if (count > 2) {
tempAns.s = name[i];
tempAns.num = count;
result.push_back(tempAns);
}
}
}
cout << result.size() << endl;
sort(result.begin(), result.end(), cmp);
for (int i = 0; i < result.size();i++) {
cout << result[i].s << " " << result[i].num << endl;
}
juSet.clear();
}
}
发表于 2019-09-06 15:50:28
回复(0)
不一定要并查集，我觉得DFS更容易理解一些，也是比较典型的解法
#include<iostream>
#include<stdio.h>
#include<string>
#include<map>
using namespace std;
/*
需要：最大人数；最大值；编号.姓名、姓名.编号、head.人数的map；连接矩阵***权；边数k；下限k；总人数numPerson；标记是否访问vis
函数：DFS; DFSTrave; 返回姓名str对应的编号; main
*/
const int maxn = 2020;//1000条边，可能2000人
const int INF = 10000000;
//map不能定义大小
map<string, int> strToint;
map<int, string> intToStr;
map<string, int> gang;
int G[maxn][maxn];
int weight[maxn];
int n = 0;
int k = 0;
int numPerson = 0;
bool vis[maxn];
void DFS(int nowVisit, int& head, int& numMember, int& totalValue)
{
vis[nowVisit] = true;
numMember++;
if (weight[nowVisit] > weight[head])
head = nowVisit;
for (int i = 0; i < numPerson; i++)
{
if (G[nowVisit][i] != 0)
{
totalValue += G[nowVisit][i];
G[nowVisit][i] = G[i][nowVisit] = 0;//拆掉回路
if (vis[i] == false)
DFS(i, head, numMember, totalValue);
}
}
}
void DFSTrave()
{
for (int i = 0; i < numPerson; i++)
{
if (vis[i] == false)
{
int head = i;
int numMember = 0;
int totalValue = 0;
DFS(i, head, numMember, totalValue);
if (totalValue > k && numMember > 2)
{
gang[intToStr[head]] = numMember;
}
}
}
}
int change(string s)
{
if (strToint.find(s) != strToint.end())
{
return strToint[s];
}
else
{
strToint[s] = numPerson;
intToStr[numPerson] = s;
return numPerson++;
}
}
int main()
{
while (cin >> n >> k)
{
string s1, s2;
int w;
for (int i = 0; i < n; i++)
{
cin >> s1 >> s2 >> w;
int u1 = change(s1);
int u2 = change(s2);
//记录每个人的通话时间
//因为可能打很多遍，所以是+=
weight[u1] += w;
weight[u2] += w;
G[u1][u2] += w;
G[u2][u1] += w;
}
DFSTrave();
map<string, int>::iterator it;//迭代器
cout << gang.size() << endl;
for (it = gang.begin(); it != gang.end(); it++)
{
cout << it->first << " " << it->second << endl;
}
}
return 0;
}
发表于 2019-08-23 13:25:00
回复(0)
/**
难度_中等题
思路：这个题倒是没什么算法，如果有算法的话，就是用了并查集，
整个过程很折腾
*/
#include
#include
#include
using namespace std;
const int N = 1000;
int father[N]={0};
struct Gang{
string s;
int num;
Gang(string ss,int a){
s=ss;
num=a;
}
Gang(){}
};
bool cmp(Gang a,Gang b){//根据题目要求，最后需要按照字典顺序输出
return a.s<b.s;
}
int findFather(int x){//并查集 查 操作
while(x!=father[x]){
x=father[x];
}
return x;
}
void Union(int a,int b){//并查集 并 操作
int fa = findFather(a);
int fb = findFather(b);
if(fa!=fb){
father[fb] = fa;
}
}
int main()
{
int n,k;
while(cin>>n>>k){
for(int i=0;i<N;i++) father[i]=i;
string from,to;
int value;
map name2num;//用于结点 字符串到数字映射
map num2name;//用于结点 数字到字符串映射
map relation;//用于记录每个结点总的和别人的通话时间
int index=0;//记录总共有多少人
for(int i=0;i<n;i++){//一波输入
cin>>from>>to>>value;
if(name2num[from]==0) {
index++;
name2num[from]=index;
num2name[index]=from;
}
if(name2num[to]==0) {
index++;
name2num[to]=index;
num2name[index]=to;
}
relation[from]+=value;
relation[to]+=value;
Union(name2num[from],name2num[to]);
}
int isVisited[N]={0};//设一个访问数组，记录那些结点访问过了
int visitNum=0;//访问的数量
int gangNum=0;//记录gang的数量
Gang gangs[N];
while(visitNum<index){
int temp;
for(int i=1;i<=index;i++){
if(isVisited[i]==0){//找一个还没访问过的结点
temp=i;
break;
}
}
int tempFather = findFather(temp);//得到这个结点的father
int totalTime = 0;
int headTime=0;
int headIndex=0;
int peoleNum=0;
//cout<<"当前团伙："<<num2name[tempFather]<<endl;
for(int i=1;i<=index;i++){
if(isVisited[i]==0){//如果这人结点还没访问
if(findFather(i)==tempFather){//并且这个人属于当前的gang
isVisited[i]=1;
visitNum++;
peoleNum++;
if(relation[(num2name[i])] > headTime){
headTime=relation[(num2name[i])];
headIndex=i;
}
totalTime+=relation[(num2name[i])];
}
}
}
if(peoleNum>2 &&totalTime>=k*2) {
Gang gang(num2name[headIndex],peoleNum);
gangs[gangNum]=gang;
gangNum++;
}
}
cout<<gangNum<<endl;
if(gangNum!=0) {
sort(gangs,gangs+gangNum,cmp);
for(int i=0;i<gangNum;i++){
cout<<gangs[i].s<<" "<<gangs[i].num<<endl;
}
}
}
return 0;
}
发表于 2019-07-01 23:03:17
回复(0)
# include<stdio.h>
# include<string.h>
# include<algorithm>
using namespace std;
struct Ans
{
char name[5];
int num;
}ans[110];
bool cmp(Ans a,Ans b)
{
int tmp=strcmp(a.name,b.name);
return tmp<0;
}
struct People
{
char name[5];
int time;
int father;
}people[1001];
struct Times
{
int father;
int time;
}timeBuf[1001];
struct Gang
{
int root;
int timeSum;
int leader;
int num;
}gang[1001];
int findRoot(int x)
{
if(people[x].father!=x)
people[x].father=findRoot(people[x].father);
return people[x].father;
}
void unit(char name1[],char name2[],int num,int bufLen)
{
int i,x,y;
int a,b;
for(i=0;i<num;i++)
{
if(strcmp(people[i].name,name1)==0) x=i;
if(strcmp(people[i].name,name2)==0) y=i;
}
a=findRoot(x);
b=findRoot(y);
if(a!=b)
people[a].father=b;
timeBuf[bufLen].father=b;
}
int main()
{
int n,m,time;
int i,j;
char name1[5],name2[5];
while(scanf("%d%d",&n,&m)!=EOF)
{
int bufLen=0;
int num=0;
while(n--)
{
scanf("%s%s%d",name1,name2,&time);
for(i=0;i<num;i++)
if(strcmp(people[i].name,name1)==0) break;
if(i==num)
{
strcpy(people[i].name,name1);
people[i].time=time;
people[i].father=i;
num++;
}
else
people[i].time=people[i].time+time;
for(i=0;i<num;i++)
if(strcmp(people[i].name,name2)==0) break;
if(i==num)
{
strcpy(people[i].name,name2);
people[i].time=time;
people[i].father=i;
num++;
}
else
people[i].time=people[i].time+time;
unit(name1,name2,num,bufLen);
timeBuf[bufLen].time=time;
bufLen++;
}
int gangLen=0;
for(i=0;i<1000;i++) gang[i].num=0;
for(i=0;i<num;i++)
{
findRoot(i);
for(j=0;j<gangLen;j++)
{
gang[j].timeSum=0;
if(gang[j].root==people[i].father)
{
gang[j].num++;
break;
}
}
if(j==gangLen)
{
gang[gangLen].root=people[i].father;
gang[gangLen].num++;
gangLen++;
}
}
int ansLen=0;
for(i=0;i<gangLen;i++)
{
if(gang[i].num>2)
{
for(j=0;j<bufLen;j++)
{
int tmp=findRoot(timeBuf[j].father);
if(tmp==gang[i].root)
gang[i].timeSum=gang[i].timeSum+timeBuf[j].time;
}
int maxTime=-1;
for(j=0;j<num;j++)
{
if(people[j].father==gang[i].root)
{
if(people[j].time>maxTime)
{
maxTime=people[j].time;
gang[i].leader=j;
}
}
}
if(gang[i].timeSum>m) ansLen++;
}
}
printf("%d\n",ansLen);
j=0;
for(i=0;i<gangLen;i++)
{
if(gang[i].num>2&&gang[i].timeSum>m)
{
strcpy(ans[j].name,people[gang[i].leader].name);
ans[j].num=gang[i].num;
j++;
}
}
sort(ans,ans+ansLen,cmp);
for(i=0;i<ansLen;i++)
printf("%s %d\n",ans[i].name,ans[i].num);
}
return 0;
}
# include<string.h>
# include<algorithm>
using namespace std;
struct Ans
{
char name[5];
int num;
}ans[110];
bool cmp(Ans a,Ans b)
{
int tmp=strcmp(a.name,b.name);
return tmp<0;
}
struct People
{
char name[5];
int time;
int father;
}people[1001];
struct Times
{
int father;
int time;
}timeBuf[1001];
struct Gang
{
int root;
int timeSum;
int leader;
int num;
}gang[1001];
int findRoot(int x)
{
if(people[x].father!=x)
people[x].father=findRoot(people[x].father);
return people[x].father;
}
void unit(char name1[],char name2[],int num,int bufLen)
{
int i,x,y;
int a,b;
for(i=0;i<num;i++)
{
if(strcmp(people[i].name,name1)==0) x=i;
if(strcmp(people[i].name,name2)==0) y=i;
}
a=findRoot(x);
b=findRoot(y);
if(a!=b)
people[a].father=b;
timeBuf[bufLen].father=b;
}
int main()
{
int n,m,time;
int i,j;
char name1[5],name2[5];
while(scanf("%d%d",&n,&m)!=EOF)
{
int bufLen=0;
int num=0;
while(n--)
{
scanf("%s%s%d",name1,name2,&time);
for(i=0;i<num;i++)
if(strcmp(people[i].name,name1)==0) break;
if(i==num)
{
strcpy(people[i].name,name1);
people[i].time=time;
people[i].father=i;
num++;
}
else
people[i].time=people[i].time+time;
for(i=0;i<num;i++)
if(strcmp(people[i].name,name2)==0) break;
if(i==num)
{
strcpy(people[i].name,name2);
people[i].time=time;
people[i].father=i;
num++;
}
else
people[i].time=people[i].time+time;
unit(name1,name2,num,bufLen);
timeBuf[bufLen].time=time;
bufLen++;
}
int gangLen=0;
for(i=0;i<1000;i++) gang[i].num=0;
for(i=0;i<num;i++)
{
findRoot(i);
for(j=0;j<gangLen;j++)
{
gang[j].timeSum=0;
if(gang[j].root==people[i].father)
{
gang[j].num++;
break;
}
}
if(j==gangLen)
{
gang[gangLen].root=people[i].father;
gang[gangLen].num++;
gangLen++;
}
}
int ansLen=0;
for(i=0;i<gangLen;i++)
{
if(gang[i].num>2)
{
for(j=0;j<bufLen;j++)
{
int tmp=findRoot(timeBuf[j].father);
if(tmp==gang[i].root)
gang[i].timeSum=gang[i].timeSum+timeBuf[j].time;
}
int maxTime=-1;
for(j=0;j<num;j++)
{
if(people[j].father==gang[i].root)
{
if(people[j].time>maxTime)
{
maxTime=people[j].time;
gang[i].leader=j;
}
}
}
if(gang[i].timeSum>m) ansLen++;
}
}
printf("%d\n",ansLen);
j=0;
for(i=0;i<gangLen;i++)
{
if(gang[i].num>2&&gang[i].timeSum>m)
{
strcpy(ans[j].name,people[gang[i].leader].name);
ans[j].num=gang[i].num;
j++;
}
}
sort(ans,ans+ansLen,cmp);
for(i=0;i<ansLen;i++)
printf("%s %d\n",ans[i].name,ans[i].num);
}
return 0;
}
发表于 2018-03-01 20:50:38
回复(0)
使用了map进行存储团伙成员的名字与整形的映射，再到后面用结构体还原出来。
#include<iostream>
#include<cstdio>
#include<map>
#define max 10005
using namespace std;
int father[max], weigh[max], flag[max];
struct gan {
string name;
int con;
};
void initial() {
for (int i = 0; i <= max; i++) {
father[i] = i;
weigh[i] = 0;
flag[i] = 0;
}
}
int find(int x) {
if (x != father[x]) father[x] = find(father[x]);
return father[x];
}
void unionxy(int x, int y,int k) {//将weigh权重直接放到main函数进行计算才更不容易出错，此处是本代码瑕点
if (find(x) != find(y)) {
father[find(y)] = find(x);
weigh[x] += k;
weigh[y] += k;
}
else {
weigh[x] += k;
weigh[y] += k;
}
}
int main() {
int n, m, x;
string s1, s2;
gan g[max];
map<string, int>mymap;
map<int, string>mymap2;
while (cin >> n >> m) {
mymap.clear();
int k = 0;
initial();
for (int i = 0; i < n; i++) {
cin >> s1 >> s2 >> x;
if (mymap.find(s1) == mymap.end()) {//未出现过则需要入散列表
mymap[s1] = k;
mymap2[k] = s1;
k++;
}
if (mymap.find(s2) == mymap.end()) {
mymap[s2] = k;
mymap2[k] = s2;
k++;
}
unionxy(mymap[s1], mymap[s2], x);
}
/*用于辅助查错
map<string, int>::iterator it;
for (it = mymap.begin(); it != mymap.end(); it++) {
cout << it->first << it->second;
}cout << endl;
for (int i = 0; i < k; i++) cout << find(i) << " ";
cout << endl;
*/
int ren = 0,gang = 0, zhong = 0;
int tag = 0;
for (int i = 0; i < k; i++) {
if (i == find(i)) {//找到连通分量
int temp = 0;
for (int j = 0; j < k; j++) {
if (i == find(j)) {//属于同一分量则入伙
ren++;
if (temp < weigh[j]) {
temp = weigh[j];
tag = j;
}
zhong += weigh[j];
}
}
// cout << zhong << "/////" << endl;
#include<cstdio>
#include<map>
#define max 10005
using namespace std;
int father[max], weigh[max], flag[max];
struct gan {
string name;
int con;
};
void initial() {
for (int i = 0; i <= max; i++) {
father[i] = i;
weigh[i] = 0;
flag[i] = 0;
}
}
int find(int x) {
if (x != father[x]) father[x] = find(father[x]);
return father[x];
}
void unionxy(int x, int y,int k) {//将weigh权重直接放到main函数进行计算才更不容易出错，此处是本代码瑕点
if (find(x) != find(y)) {
father[find(y)] = find(x);
weigh[x] += k;
weigh[y] += k;
}
else {
weigh[x] += k;
weigh[y] += k;
}
}
int main() {
int n, m, x;
string s1, s2;
gan g[max];
map<string, int>mymap;
map<int, string>mymap2;
while (cin >> n >> m) {
mymap.clear();
int k = 0;
initial();
for (int i = 0; i < n; i++) {
cin >> s1 >> s2 >> x;
if (mymap.find(s1) == mymap.end()) {//未出现过则需要入散列表
mymap[s1] = k;
mymap2[k] = s1;
k++;
}
if (mymap.find(s2) == mymap.end()) {
mymap[s2] = k;
mymap2[k] = s2;
k++;
}
unionxy(mymap[s1], mymap[s2], x);
}
/*用于辅助查错
map<string, int>::iterator it;
for (it = mymap.begin(); it != mymap.end(); it++) {
cout << it->first << it->second;
}cout << endl;
for (int i = 0; i < k; i++) cout << find(i) << " ";
cout << endl;
*/
int ren = 0,gang = 0, zhong = 0;
int tag = 0;
for (int i = 0; i < k; i++) {
if (i == find(i)) {//找到连通分量
int temp = 0;
for (int j = 0; j < k; j++) {
if (i == find(j)) {//属于同一分量则入伙
ren++;
if (temp < weigh[j]) {
temp = weigh[j];
tag = j;
}
zhong += weigh[j];
}
}
// cout << zhong << "/////" << endl;
if (zhong/2 > m && ren > 2) {//每个weigh算了两次，需要除以2
g[gang].name = mymap2[tag];
g[gang].con = ren;
gang++;
}
ren = 0;
zhong = 0;
}
}
cout << gang << endl;
for (int i = 0; i < gang; i++) {
cout << g[i].name << " " << g[i].con << endl;
}
}
return 0;
}
g[gang].name = mymap2[tag];
g[gang].con = ren;
gang++;
}
ren = 0;
zhong = 0;
}
}
cout << gang << endl;
for (int i = 0; i < gang; i++) {
cout << g[i].name << " " << g[i].con << endl;
}
}
return 0;
}
编辑于 2024-02-27 18:16:12
回复(0)
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
