PAT甲级 1034 Head of a Gang （30分）

原题链接 PAT甲级 1034 Head of a Gang （30分）


题目大意 假如A和B有通话，就称他们是有关系的。并且A和B之间的权值就是他们通话的时间。一个匪帮被假定为有两个人以上，以及他们之间的权值之和（也就是通话时间之和）超过一个给定的阈值K。在每个匪帮中首领被定义为权值最大的人。现在你需要找出匪帮以及其首领。


分析
1、显然这是道图的问题。匪帮的个数也就是图的连通分量，可以先用DFS求出图的连通分量，判断各个连通分量的顶点个数是否超过2以及权值之和是否超过阈值K。
2、把名字转换为序号，便于构造邻接矩阵以及记录总人数
3、输出要按首领名字字母顺序输出，所以在找到首领和匪帮人数之后先保存在一个vector<node>里面，node是个结构体，保存了首领名字和匪帮人数。然后根据名字对vector排序，输出最终结果。不然会有两个测试点通过不了。

#include<iostream>
#include<map>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;
int n, k, t, num=1, cnt=0;
string s1, s2;
map<string, int> sti;
map<int, string> its;
int adj[2002][2002], w[2002];
bool visit[2002] = {false};
vector<int> com[2002];
struct node{
    string name;
    int num;
};
vector<node> ans;
bool cmp(node n1, node n2){
    return n1.name < n2.name;
}
void dfs(int v){
    com[cnt].push_back(v);
    visit[v]=true;
    for(int i=1;i<num;i++){
        if(!visit[i] && adj[v][i]!=0){
            dfs(i);
        }           
    }
}
int strtoid(string s){
    if(sti[s]==0){
        sti[s] = num;
        its[num] = s;
        return num++;
    } 
    return sti[s];      
}
bool isgang(vector<int> v){
    if(v.size()<=2) return false;
    int maxw = 0;
    for(int i=0;i<v.size();i++){
        maxw += w[v[i]];
    }
    if(maxw/2 > k)  return true;
    return false;
}
int main(){
    scanf("%d%d", &n, &k);
    for(int i=0;i<n;i++){
        cin>>s1>>s2;
        int id1 = strtoid(s1);
        int id2 = strtoid(s2);
        scanf("%d", &t);
        adj[id1][id2] = adj[id2][id1] = t;
        w[id1] += t;
        w[id2] += t;
    }
    for(int i=1;i<num;i++){
        if(visit[i]==false){
            dfs(i);
            if(isgang(com[cnt]))
                cnt++;
            else
                com[cnt].clear();
        }
    }
    printf("%d\n", cnt);
    ans.resize(cnt);
    for(int i=0;i<cnt;i++){
        int maxid = com[i][0], nm = com[i].size();
        for(int j=1;j<com[i].size();j++){       
            if(w[maxid] < w[com[i][j]])
                maxid = com[i][j];
        }       
        ans[i] = {its[maxid], nm};
    }
    sort(ans.begin(), ans.end(), cmp);
    for(int i=0;i<cnt;i++){
        cout<<ans[i].name<<" "<<ans[i].num<<endl;
    }
    return 0;
}