題目描述

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.

Input Specification:
Each input file contains one test case. 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.

Output Specification:
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.

Sample Input 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

Sample Output 1:
2
AAA 3
GGG 3

Sample Input 2:
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
Sample Output 2:
0

問題分析

該題輸入n個(gè)通話記錄和一個(gè)閾值k骇两，一個(gè)通話記錄是由通話雙方兩個(gè)節(jié)點(diǎn)組成，定義通話雙方的通話時(shí)長(zhǎng)為每一次的通話之和援岩，比如A->B 10驹暑，B->A 20谚鄙，A和B的通話時(shí)長(zhǎng)=10+20=30，所以n個(gè)通話記錄組成了一個(gè)通話圖，由上述定義可知顾翼，該圖是無向圖台腥，題目要求從該圖中找出所有的符合條件的連通圖里的節(jié)點(diǎn)個(gè)數(shù)和head節(jié)點(diǎn)宏赘，要求該連通圖的節(jié)點(diǎn)數(shù)大于2，并且該連通圖的邊權(quán)和大于閾值k览爵，head節(jié)點(diǎn)是一個(gè)連通圖中相鄰邊權(quán)值最大的節(jié)點(diǎn)置鼻，比如A---B 30, A---C 40，那么A-B-C形成了一個(gè)Gang蜓竹，并且head的點(diǎn)權(quán)=30+40=70箕母，B的點(diǎn)權(quán)=30储藐，C的點(diǎn)權(quán)=40，因此A節(jié)點(diǎn)是該Gang里的head嘶是。

根據(jù)以上分析钙勃，我們要解決的問題：

• 圖的定義：由于通話記錄少于1000條，因此節(jié)點(diǎn)不超過2000個(gè)聂喇，定義圖的邊權(quán)為通話雙方通話記錄之和辖源。
• 點(diǎn)權(quán)的定義：為了找到一個(gè)Gang里的head，定義點(diǎn)權(quán)為該節(jié)點(diǎn)鄰接所有節(jié)點(diǎn)的邊權(quán)之和希太。
• 姓名和編號(hào)的映射：由于輸出的是姓名字符串克饶，我們需要將姓名映射到節(jié)點(diǎn)編號(hào)，使用map<string,int>,map<int,string>誊辉。
• 求解符合條件的連通圖 ：可以使用BFS或者DFS遍歷矾湃，注意在每次遍歷時(shí)，記錄邊權(quán)和堕澄，更新head節(jié)點(diǎn)邀跃。此外，由于在計(jì)算邊權(quán)和的時(shí)候蛙紫，出現(xiàn)一個(gè)節(jié)點(diǎn)鄰接一個(gè)已訪問的環(huán)拍屑，會(huì)重復(fù)計(jì)算邊權(quán)，這里使用刪除策略坑傅，在對(duì)邊權(quán)累加結(jié)束后僵驰，刪除該邊，再進(jìn)行DFS或者BFS遍歷裁蚁。

參考代碼

#include<iostream>
#include<map>
#include<string>

using namespace std;

const int maxn = 2010;
const int INF = 100000000;

map<int,string> intToString; //編號(hào)和姓名對(duì)應(yīng)
map<string,int> stringToInt; //姓名和編號(hào)對(duì)應(yīng)
map<string,int> Gang; //head->人數(shù)

//使用鄰接矩陣存儲(chǔ)
//weight:是每一個(gè)點(diǎn)的點(diǎn)權(quán)矢渊，為其鄰接點(diǎn)的邊權(quán)之和
int graph[maxn][maxn] = {0},weight[maxn] = {0};
int n,k,numPerson = 0;
bool vis[maxn] = {false};

//DFS訪問連通塊
//nowVisit是現(xiàn)在訪問節(jié)點(diǎn)，head是當(dāng)前的頭目枉证，numMember是當(dāng)前的人數(shù)矮男，totalValue是當(dāng)前的總邊權(quán)
void DFS(int nowVisit,int& head,int& numMember,int& totalValue)
{
    //人數(shù)+1
    numMember ++;
    //設(shè)置訪問標(biāo)志
    vis[nowVisit] = true;
    //更新頭目
    if(weight[nowVisit] > weight[head])
    {
        head = nowVisit;
    }
    //訪問當(dāng)前節(jié)點(diǎn)的所有的鄰接點(diǎn)
    for(int i=0;i<numPerson;i++) //枚舉所有人
    {
        //如果當(dāng)前節(jié)點(diǎn)， 能夠到達(dá)i節(jié)點(diǎn)
        if(graph[nowVisit][i]>0)
        {
            //累加邊權(quán)
            totalValue += graph[nowVisit][i];
            //為了防止走回頭路室谚，邊權(quán)的重復(fù)累加毡鉴，刪除該條邊
            graph[nowVisit][i] = graph[i][nowVisit] = 0;
            //如果節(jié)點(diǎn)i未被訪問， 則DFS訪問其臨界點(diǎn)
            if(vis[i] == false)
            {
                DFS(i,head,numMember,totalValue);
            }
        }
    }
}

//遍歷整個(gè)圖秒赤，獲取每個(gè)連通塊的信息
void DFSTravel()
{
    for(int i=0;i<numPerson;i++)
    {
        if(vis[i] == false)
        {
            //初始化頭目猪瞬，連通圖成員數(shù)，總邊權(quán)
            int head = i,numMember = 0,totalValue = 0;
            DFS(i,head,numMember,totalValue);
            //判斷是否滿足題目要求入篮，成員數(shù)大于2陈瘦，并且總邊權(quán)要大于k
            if(numMember>2 && totalValue >k)
            {
                //記錄Gang信息
                Gang[intToString[head]] = numMember;
            }
        }
    }
}

//定義change函數(shù)，表示int和str的對(duì)應(yīng)關(guān)系
int change(string str)
{
    if(stringToInt.find(str) != stringToInt.end())
    {
        //如果該姓名出現(xiàn)過潮售，那么返回該節(jié)點(diǎn)編號(hào)
        return stringToInt[str];
    }
    else
    {
        //若沒出現(xiàn)過痊项，那么新增該姓名
        stringToInt[str] = numPerson;
        intToString[numPerson] = str;
        //返回編號(hào)锅风，這里使用給變量numPerson來控制節(jié)點(diǎn)的增加，需要學(xué)習(xí)
        return numPerson++;

    }
}

int main()
{
    int w;
    string str1,str2;
    cin>>n>>k;
    for(int i=0;i<n;i++)
    {
        cin>>str1>>str2>>w;
        //找到或者賦給str1和str2的編號(hào)
         int id1= change(str1);
         int id2 = change(str2);
         //圖的邊權(quán)賦值,由于是無向圖鞍泉，雙向增加
         graph[id1][id2] += w;
         graph[id2][id1] +=w;
         //點(diǎn)權(quán)賦值
         weight[id1] += w;
         weight[id2] += w;
    }
    //遍歷所有連通塊
    DFSTravel();
    //打印Gang的個(gè)數(shù)
    cout<<Gang.size()<<endl;
    //打印Gang
    map<string,int>::iterator it;
    for(it = Gang.begin();it != Gang.end();it++)
        cout<<it->first<<" "<<it->second<<endl;
    return 0;
}