PAT 解题报告 1034. Head of a Gang (30)


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.

不翻译了>_< 下面算法分析的时候有解释.


抽象出来, 其实这个题目就是给你一个图(不一定全部联通), 图的边有权重, 让找到所有的联通分量, 这个联通分量的权重(所有边的权重之和) 大于某个给定的阀值的时候, 这个联通分量就是一个gang, 这个gang里面权重最大那个节点(节点的权重定义成链接到这个节点的边的权重之和)就是这个gang的头目, 按照名字的字典序输出所有这样的gang和头目以及这个gang的节点数.

算法就是dfs寻找联通子图,dfs的同时计算出所有需要的数据(e.g., 子图的权重). 不难. 代码如下:

#include <iostream>

#include <cstdio>
#include <cstring>

#include "stdio.h"

#include "math.h"
#include <algorithm>
#include <vector>
#include <map>

#include <iomanip>

#define MAX(a,b) (a>b)?a:b
#define REP(i,n) for(i=0;i<(n);++i)  

#define NNodes 2010
using namespace std;

typedef struct {
    string name;
    int wgt;
} Member;

Member members[NNodes];
Member res[1000];

map<string, int> names;

int adjList[NNodes][NNodes];
int disJointSet[NNodes];
int classes;

int N, K;

void dfsUnion(int root, int N, int *count, int *total, int* head) {
    disJointSet[root] = classes;
    (*count) = (*count) + 1;
    if(members[*head].wgt < members[root].wgt ) 
        *head = root;
    for(int i=1; i<=N; i++) {
        if(adjList[root][i]) {
            (*total) += adjList[root][i];
    for(int i=1; i<=N; i++) 
        if(adjList[root][i] && !disJointSet[i]) {
            dfsUnion(i, N, count, total, head);

int compare(const void *elem1, const void *elem2)
     return (((Member*)(elem1))->name).compare(((Member*)(elem2))->name); 

int main(void) {
    int id = 0;
    for(int i=0; i<N; i++) {
        string a; string b; int weight;
            names[a] = ++id;
            names[b] = ++id;

        adjList[names[a]][names[b]] = adjList[names[b]][names[a]] =
            adjList[names[a]][names[b]] + weight;
        members[names[a]].name = a; members[names[a]].wgt += weight;
        members[names[b]].name = b; members[names[b]].wgt += weight;

    memset(disJointSet, 0, sizeof(int)*NNodes);
    classes = 0;
    int len = 0;
    for(int i=1; i<=id; i++) {
        if(!disJointSet[i]) {
            int numOfMem = 0;
            int totalWeight = 0;
            int head = i;

            dfsUnion(i, id, &numOfMem, &totalWeight, &head);
            if(numOfMem>2 && totalWeight/2>K) {
               res[len].name = members[head].name;
               res[len++].wgt = numOfMem;
    if(len) {
        qsort(res, len, sizeof(Member), compare);
        for(int j=0; j<len; j++) {
            cout<<res[j].name<<" "<<res[j].wgt<<endl; 
    else {
    return 0;

Written on August 3, 2013