1034.Head of a Gang (30)
pat-al-1034
2017-02-04
圖的遍歷，連通分量，dfs對于每一個連通分量，要求其head和包含的成員個數，以及該gang的總權值套路：用map來映射名稱和序號、visited、邊e、節點權重weight練習了用迭代器輸出map的內容坑見注釋/** * pat-al-1034 * 2017-02-04 * Cpp version * Author: fengLian_s */#include<stdio.h>#include<iostream>#include<map>#include<string>#define MAX 2003//坑……我還以為是1000，導致段錯誤using namespace std;int k;int maxNumberOfPeople = 1;int visited[MAX], weight[MAX], e[MAX][MAX];map<string, int> str2int;map<int, string> int2str;map<string, int> result;int string2int(string s){ if(str2int[s] == 0)//還未放入映射中 { str2int[s] = maxNumberOfPeople; int2str[maxNumberOfPeople] = s; //cout << s << ": " << maxNumberOfPeople << endl; return maxNumberOfPeople++; } else return str2int[s];}void dfs(int u, int &head, int &numberOfMember, int &totalWeight){ visited[u] = 1; numberOfMember++; if(weight[u] > weight[head]) head = u; for(int v = 1;v < maxNumberOfPeople;v++) { if(e[u][v] != 0)//坑：和下面的visited必須要分開判斷，此處判斷的是是否有邊沒有加入總權重 { totalWeight += e[u][v]; //-FIN-新聞熱點
疑難解答
