PATA1034-Head of Gang

題目描述

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;
}
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 序言:七十年代末皱埠,一起剝皮案震驚了整個(gè)濱河市,隨后出現(xiàn)的幾起案子咖驮,更是在濱河造成了極大的恐慌边器,老刑警劉巖,帶你破解...
    沈念sama閱讀 222,681評(píng)論 6 517
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件托修,死亡現(xiàn)場(chǎng)離奇詭異忘巧,居然都是意外死亡,警方通過查閱死者的電腦和手機(jī)睦刃,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,205評(píng)論 3 399
  • 文/潘曉璐 我一進(jìn)店門袋坑,熙熙樓的掌柜王于貴愁眉苦臉地迎上來,“玉大人眯勾,你說我怎么就攤上這事∑攀模” “怎么了吃环?”我有些...
    開封第一講書人閱讀 169,421評(píng)論 0 362
  • 文/不壞的土叔 我叫張陵,是天一觀的道長(zhǎng)洋幻。 經(jīng)常有香客問我郁轻,道長(zhǎng),這世上最難降的妖魔是什么文留? 我笑而不...
    開封第一講書人閱讀 60,114評(píng)論 1 300
  • 正文 為了忘掉前任好唯,我火速辦了婚禮,結(jié)果婚禮上燥翅,老公的妹妹穿的比我還像新娘骑篙。我一直安慰自己,他們只是感情好森书,可當(dāng)我...
    茶點(diǎn)故事閱讀 69,116評(píng)論 6 398
  • 文/花漫 我一把揭開白布靶端。 她就那樣靜靜地躺著,像睡著了一般凛膏。 火紅的嫁衣襯著肌膚如雪杨名。 梳的紋絲不亂的頭發(fā)上,一...
    開封第一講書人閱讀 52,713評(píng)論 1 312
  • 那天猖毫,我揣著相機(jī)與錄音台谍,去河邊找鬼。 笑死吁断,一個(gè)胖子當(dāng)著我的面吹牛趁蕊,可吹牛的內(nèi)容都是我干的坞生。 我是一名探鬼主播,決...
    沈念sama閱讀 41,170評(píng)論 3 422
  • 文/蒼蘭香墨 我猛地睜開眼介衔,長(zhǎng)吁一口氣:“原來是場(chǎng)噩夢(mèng)啊……” “哼恨胚!你這毒婦竟也來了?” 一聲冷哼從身側(cè)響起炎咖,我...
    開封第一講書人閱讀 40,116評(píng)論 0 277
  • 序言:老撾萬榮一對(duì)情侶失蹤赃泡,失蹤者是張志新(化名)和其女友劉穎,沒想到半個(gè)月后乘盼,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體升熊,經(jīng)...
    沈念sama閱讀 46,651評(píng)論 1 320
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡,尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 38,714評(píng)論 3 342
  • 正文 我和宋清朗相戀三年绸栅,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了级野。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
    茶點(diǎn)故事閱讀 40,865評(píng)論 1 353
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡粹胯,死狀恐怖蓖柔,靈堂內(nèi)的尸體忽然破棺而出,到底是詐尸還是另有隱情风纠,我是刑警寧澤况鸣,帶...
    沈念sama閱讀 36,527評(píng)論 5 351
  • 正文 年R本政府宣布,位于F島的核電站竹观,受9級(jí)特大地震影響镐捧,放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜臭增,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 42,211評(píng)論 3 336
  • 文/蒙蒙 一懂酱、第九天 我趴在偏房一處隱蔽的房頂上張望。 院中可真熱鬧誊抛,春花似錦列牺、人聲如沸。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,699評(píng)論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽(yáng)。三九已至并炮,卻和暖如春默刚,著一層夾襖步出監(jiān)牢的瞬間,已是汗流浹背逃魄。 一陣腳步聲響...
    開封第一講書人閱讀 33,814評(píng)論 1 274
  • 我被黑心中介騙來泰國(guó)打工荤西, 沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留,地道東北人。 一個(gè)月前我還...
    沈念sama閱讀 49,299評(píng)論 3 379
  • 正文 我出身青樓邪锌,卻偏偏與公主長(zhǎng)得像勉躺,于是被迫代替她去往敵國(guó)和親。 傳聞我的和親對(duì)象是個(gè)殘疾皇子觅丰,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 45,870評(píng)論 2 361

推薦閱讀更多精彩內(nèi)容