头像

TracyGeorge




离线:7小时前



#include<iostream>
#include<vector>
#include<algorithm>
#include<unordered_map>
using namespace std;
int n,k;
unordered_map<string,vector<string>> g;//每个人都有一个自己的通话对象名字的数组。
unordered_map<string,int> total;//每个人各自的通话时间总长
unordered_map<string,bool> st;//判断是否计算过某个人的通话时长
int dfs(string name,vector<string>&nodes){
    st[name]=true;
    nodes.push_back(name);
    int sum=total[name];
    for(auto c:g[name]) if(!st[c]) sum+=dfs(c,nodes);   
    return sum;
}
int main(){
    scanf("%d %d",&n,&k);
    while(n--){
        string name_1,name_2;
        int time;
        cin>>name_1>>name_2>>time;
        g[name_1].push_back(name_2), g[name_2].push_back(name_1);
        total[name_1]+=time, total[name_2]+=time;
    }
    vector<pair<string,int>>res;
    for(auto c:total){
        string name=c.first;
        vector<string> nodes;
        int sum=0;
        if(!st[name]) sum=dfs(name,nodes)/2;
        if(sum>k&&nodes.size()>2){
            string boss=nodes[0];
            for(auto temp: nodes) if(total[temp]>total[boss]) boss=temp;
            res.push_back({boss,nodes.size()});
        }
    }
    sort(res.begin(),res.end());
    printf("%d\n",res.size());
    for(auto c: res) printf("%s %d\n",c.first.data(),c.second);
    return 0;
}



1.因为子节点的高度是父节点高度+1,所以在bfs所有节点的同时,可以更新最大个数,和其对应的层数。
2.储存方式是邻接表
#include<iostream>
#include<vector>
#include<string.h>
#define N 110
using namespace std;
int e[N],ne[N],h[N],cnt[N];
int idx=0,n,m,id,k,son,max_cnt=0,max_level=0;
void add(int a,int b){
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void dfs(int root,int level){
    cnt[level]++;
    if(max_cnt<cnt[level]) max_cnt=cnt[level],  max_level=level;
    for(int i=h[root];i!=-1;i=ne[i]) dfs(e[i],level+1); 
}
int main(){
    memset(h,-1,sizeof(h));
    scanf("%d %d",&n,&m);
    while(m--){
        scanf("%d %d",&id,&k);
        while(k--){
            scanf("%d",&son);
            add(id,son);
        }
    }
    dfs(1,1);
    printf("%d %d",max_cnt,max_level);
}


活动打卡代码 AcWing 1519. 密码

//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~

include[HTML_REMOVED]

include[HTML_REMOVED]

typedef struct{
char name[15];
char pws[15];
int flag;
}account;
char change(char pws,char *re){
int n=strlen(pws);
for(int i=0;i<n;i){
if(pws[i]==‘1’) re[i]=’@’;
else if(pws[i]==‘0’) re[i]=’%’;
else if(pws[i]==’l’) re[i]=’L’;
else if(pws[i]==’O’) re[i]=’o’;
else re[i]=pws[i];
}
return re;
}
int main(){
int n,m=0;
account arr[1005];
scanf(“%d”,&n);
for(int i=0;i<n;i
){
memset(arr[i].name,0,sizeof(arr[i].name));
memset(arr[i].pws,0,sizeof(arr[i].pws));
scanf(“%s %s”,&arr[i].name,&arr[i].pws);
arr[i].flag=0;
}
for(int i=0;i<n;i){
char new_pws[15];
char re[15];
memset(re,0,sizeof(re));
memset(new_pws,0,sizeof(new_pws));
strcpy(new_pws,change(arr[i].pws,re));
if(strcmp(new_pws,arr[i].pws)){
strcpy(arr[i].pws,new_pws);
arr[i].flag=1;
m
;
}
}
if(m==0){
if(n==1) {
printf(“There is 1 account and no account is modified”);
return 0;
}
else {
printf(“There is %d accounts and no account is modified”,n);
return 0;
}
}
else {
printf(“%d\n”,m);
for(int i=0;i<n;i++){
if(arr[i].flag==1) printf(“%s %s\n”,arr[i].name,arr[i].pws);
}
return 0;
}
}