PAT A1034 Head of a Gang

题目链接

解题思路

这个题目非常难顶奥，主要是使用DFS。

1、首先要将每一个姓名字符串转为从0开始的编号，可以使用两个map将字符串和int编号一一对应。没对应一个字符串，personId要加一，表示总人数。

2、然后就定义一个一维数组weight表示点权和一个二维数组G表示边权，为了防止DFS遍历的时候重复，就把平行边直接设置为他们的和，然后在DFS遍历的时候，只要G加一次，就把这个边直接设置为0，相当于删掉这条边即可。

3、然后设置一个vis数组表示当前节点是否访问，开始遍历每一个人，如果vis为false，说明没有遍历过，就进入DFS进行遍历，这里的三个函数形式参数head，numMember和totalValue就相当于函数的返回值，在DFS递归的过程中不断更新，最后根据numMember和totalValue来判断是否是Gang，并记录。

代码

#include <iostream>
#include <string>
#include <map>
using namespace std;
const int maxn=2010;//因为每次电话记录最多有1000条，所以不同的人的权重最大为2000
int n,k,personId=0,weight[maxn]={0},G[maxn][maxn]={0};
bool vis[maxn]={false};
map<string,int> stringToint;
map<int,string> intTostring;
map<string,int> Gang;

//将字符串与id对应
int change(string str){
    if(stringToint.find(str)!=stringToint.end()){//map中已有该字符串对应id
        return stringToint[str];
    }else{//没有的话就再加入进去
        stringToint[str]=personId;
        intTostring[personId]=str;
        return personId++;
    }
}

void DFS(int nowVisit,int& head,int& numMember,int& totalValue){
    numMember++;//dfs一次就说明Gang的成员加一
    vis[nowVisit]=true;//然后把当前节点标记为已访问
    if(weight[nowVisit]>weight[head]){//如果当前节点权值大于head，就把head设为最大
        head=nowVisit;
    }
    for(int i=0;i<personId;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 DFSTravel(){
    for(int i=0;i<personId;i++){
        if(vis[i]==false){
            int head=i,numMember=0,totalValue=0;//这里head要等i，因为是这一组中的head
            DFS(i,head,numMember,totalValue);
            if(numMember>2&&totalValue>k){
                Gang[intTostring[head]]=numMember;
            }
        }
    }
}

int main(){
    cin>>n>>k;
    string s1,s2;
    int w;
    for(int i=0;i<n;i++){
        cin>>s1>>s2>>w;
        int id1=change(s1);
        int id2=change(s2);
        //the one with maximum total weight is the head
        //为了求每个Gang里的head，将每个节点的点权相加,保存在数组weight中
        weight[id1]+=w;
        weight[id2]+=w;
        //为了判断个Gang总权值是否超过阈值K，就把无向图的两条边平行边合并为一条,后面只要访问了一次即可
        G[id1][id2]+=w;
        G[id2][id1]+=w;
    }
    DFSTravel();
    cout<<Gang.size()<<endl;
    //因为map再加入的时候就会将key自动排序，所以就是按姓名的字典序排好的
    for(auto it=Gang.begin();it!=Gang.end();it++){
        cout<<it->first<<" "<<it->second<<endl;
    }

    return 0;
}