关于算法-数据结构:PAT甲级1034-Head-of-a-Gang

题目粗心：

给出若干人之间的通话长度, 依照这些通话将他们分成若干个组。当初给定一个犯罪团伙，而该组内点权最大的人视为喽罗。要求输入犯罪团伙的个数, 并且依照喽罗姓名字典序从小到大的程序输入每个犯罪团伙的喽罗姓名和成员个数。

算法思路：

这道题的题意得先了解分明,

In each gang, the one with maximum total weight is the head.

这句话的意思是 $maximum$ $total$ $weight$ 的点为 $head$, 然而 $weight$ 在题目中是边权, 所以这里针对题目的案例进行手动绘图和假如后, 比拟正当的解释就是一个点的 $total$ $weight$ 指的是该点出边和入边的边权的和。并且依据语义来说，该图应该是一个无向图，因为通话是建设单方的连贯.

接下来咱们要晓得咱们须要取得那些信息能够求解这些问题, 以及通过什么形式取得这些数据, 题目要求输入每个犯罪团伙的喽罗姓名和成员个数, 首先犯罪团伙的定义是一个团伙 (连通重量) 其人数大于 2 并且总边权的和大于 K, 而后头目标定义是组内点权最大的人视为喽罗, 那么咱们要取得信息如下：

 1)组内的人数(连通重量的结点个数)
 2)组内的通话时间总和(连通重量的总边权)
 3)组内通话时间最长的人(连通重量中点权最大的结点编号)

当初晓得了须要取得下面 3 条信息后, 就得晓得如何取得 3 条信息, 这些信息都与连通重量无关, 在图中咱们取得每个结点或者连通重量信息的办法就是遍历, 这里应用了 DFS。

在进行 DFS 遍历之前得先对数据进行预处理:

• 输出的名字是字符串, 咱们遍历的是结点编号, 同时输入的时候也是字符串, 那么得建设名字 —> 结点编号, 结点编号 —–> 名字的双向映射, 这里应用 unordered_map<int,string> indexToName 存储编号到姓名的映射，unordered_map<string,int> nameToIndex存储姓名到编号的映射，具体的做法就是先应用 numPerson=0 示意以后已知结点的个数, 同时也是新退出图中的结点的编号，在每次输出数据的时候先判断以后人的名字是否呈现过, 如果没有呈现就建设名字和结点编号的映射和编号和名字的反映射，否则就取出该名字的编号，紧接着就依据编号，累计点权和边权。

DFS 遍历过程：

每一次 DFS 须要取得以上 3 条信息并且每次遍历一个连通重量, 咱们设置参数 start,number,total_time,head 别离代表以后拜访结点, 以后连通重量的结点个数, 边权总和和最大点权的编号, 每次拜访结点就累加连通重量的结点个数 ++number，并且判断以后结点的点权和head 的点权哪个更大, 如果以后结点更大，更新head，而后再遍历其邻接点, 这里有个留神点, 因为有可能是有环的图, 所以为了计算总边权, 咱们先累加以后结点和邻接点的边权, 而后再判断邻接点是否能够拜访。并且每一条边只能拜访一次，所以在每次拜访后，就将该条边进行赋值为 0，这样保障在反复拜访的时候总边权计算不会出错，之所以先累计边权，看下图即可：

接下来可就是遍历整个图形取得所有连通重量的那 3 个信息, 对于每一个顶点只有没有拜访就调用 DFS 拜访该连通重量, 而后将取得的信息进行解决, 只有 number>2&&total_time>K 阐明是犯罪团伙, 那么记录犯罪团伙的喽罗和人数, 这里采纳 map<string,int> result 记录，因为能够主动排序, 具体操作为 result[indexToName[head]] = number;
最初依照要求输入即可

留神点;

• 1. 测试点 3 呈现段谬误, 起因在于数组开的太小了,n 条边最多有 2 * n 个结点，至多开到 2000 以上
• 2. 没有排序测试点 2 和 5 谬误
• 3、没有思考到一个团伙有 2 个点权一样大输入字典序小的测试点 5 谬误, 间接在遍历图的时候依照结点编号从小到大进行遍历就能够防止
• 4、题目说A name is a string of three capital letters chosen from A-Z，并不是名字都是 AAA,BBB 这种 3 个字母都一样的名字, 只不过样例给的是这样的, 有误导作用, 不然只能过 2 个测试点(不要问我是怎么晓得的，(╥╯^╰╥))，所以应用从 0 开始顺次递增赋值编号是最不便的，字符串 hash 这里不太实用，容易超内存。

提交后果:

很多网上的代码只能通过 PAT 的测试点, 无奈通过牛客网的测试, 自己提供的代码, 均能通过.

AC 代码：

#include <cstdio>
#include <vector>
#include <iostream>
#include <unordered_map>
#include <map>

using namespace std;

int N,K;// 边数和阈值
bool visited[2000];// 拜访标记数组
int G[2000][2000];// 邻接矩阵，其值为边权
int node_weight[2000];// 点权
unordered_map<int,string> indexToName;// 存储编号到姓名的映射
unordered_map<string,int> nameToIndex;// 存储姓名到编号的映射
map<string,int> result;// 每一个 gang 的 head 和人数汇合
int numPerson = 0;// 总人数

void DFS(int start,int &number,int &total_time,int &head){visited[start] = true;// 拜访该节点
    ++number;// 以后连通重量节点数目加一
    if(node_weight[head]<node_weight[start]){
        // 更新 head
        head = start;
    }
    // 遍历每一个领接点
    for(int i=0;i<numPerson;++i){if(G[start][i]!=0){
            // i 是 start 的领接点
            total_time += G[start][i];// 先累计总时长, 为了防止出现环的时候少拜访一条边
            // start->i 的边只能拜访一遍, 得置为 0，避免反复计算影响后果
            G[start][i] = G[i][start] = 0;
            if(!visited[i]){DFS(i,number,total_time,head);
            }
        }
    }
}

void DFSTraverse(){for (int i = 0; i < numPerson; ++i) {if(!visited[i]){
            int number = 0;// 每一个 gang 的人数
            int total_time = 0;// 每一个 gang 的总通话时长
            int head = i;// 每一个 gang 的 head, 初始得是以后拜访连通块中的点，不能是 0
            DFS(i,number,total_time,head);
            if(number>2&&total_time>K){
                // 以后连通重量是一个 gang
                result[indexToName[head]] = number;
            }
        }
    }
    printf("%lu\n",result.size());
    map<string,int>::iterator it;
    for(it=result.begin();it!=result.end();++it){printf("%s %d\n",it->first.c_str(),it->second);
    }
}

int main()
{scanf("%d %d",&N,&K);
    string a,b;
    int time,index_a,index_b;
    for (int i = 0; i < N; ++i) {
        cin>>a>>b>>time;
        if(nameToIndex.find(a)==nameToIndex.end()){
            // 第一次呈现, 赋予编号
            index_a = numPerson++;
            nameToIndex[a] = index_a;
            indexToName[index_a] = a;
        } else {
            // 不是第一次呈现，取出编号
            index_a = nameToIndex[a];
        }
        if(nameToIndex.find(b)==nameToIndex.end()){
            // 第一次呈现, 赋予编号
            index_b = numPerson++;
            nameToIndex[b] = index_b;
            indexToName[index_b] = b;
        } else {
            // 不是第一次呈现，取出编号
            index_b = nameToIndex[b];
        }
        // 边权
        G[index_a][index_b] += time;
        G[index_b][index_a] += time;
        // 点权
        node_weight[index_a] += time;
        node_weight[index_b] += time;
    }
    DFSTraverse();
    return 0;
}