pat 甲级 A1034 Head of a Gang (30分)_pat a1034 head of a gang-CSDN博客

本文链接：https://blog.csdn.net/dutmathjc/article/details/105784667

本文介绍了一种基于图的聚类算法实现，该算法通过深度优先搜索（DFS）遍历图来寻找满足特定条件的簇，即簇内成员数量超过两人且权重总和超过给定阈值。代码使用C++实现，包括节点权重计算、图的构建以及遍历算法。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

题目链接：

https://pintia.cn/problem-sets/994805342720868352/problems/994805456881434624

题目分析：

本题有两点需要注意，在一个簇中，1，人数必须大于两人；2，权重和必须大于给定的阈值。

参考代码：

#include<iostream>
#include<string>
#include<map>
using namespace std;
const int maxn=2010;
const int INF=1e9;

map<int, string> inttostring;
map<string, int> stringtoint;
map<string, int> gang;
int  G[maxn][maxn]={0},weight[maxn]={0};
int  n,k,numperson=0;
bool vis[maxn]={false};

void  DFS(int nowmember, int& head, int& nummember, int& totalvalue){
    nummember++;
    vis[nowmember] = true;
    if(weight[nowmember] > weight[head]) head = nowmember;
    for(int i = 0;i < numperson; i++){
        if(G[nowmember][i] > 0){
            totalvalue += G[nowmember][i];
            G[nowmember][i] = G[i][nowmember] = 0;
            if(vis[i]==false)  DFS(i,head,nummember,totalvalue); 
        }
    }
}

void  DFSTrave(){
    for(int i=0;i<numperson;i++){
        if(vis[i]==false){
            int head=i,nummember=0,totalvalue=0;
            DFS(i,head,nummember,totalvalue);
            if(nummember>2&&totalvalue>k)    gang[inttostring[head]]=nummember;
        }
    }
}

int change(string str){
    if(stringtoint.find(str)!=stringtoint.end()){
        return stringtoint[str];
    }else{
        stringtoint[str]=numperson;
        inttostring[numperson]=str;
        return numperson++;
    }
}

int main()
{
    int  w;
    string str1,str2;
    cin>>n>>k;
    for(int i = 0; i < n; i++){
        cin >> str1 >> str2 >> w;
        int id1 = change(str1);
        int id2 = change(str2);
        weight[id1] += w;
        weight[id2] += w;
        G[id1][id2] += w;
        G[id2][id1] += w;
    }
    DFSTrave();
    cout << gang.size() << endl;
    for(auto it = gang.begin(); it != gang.end(); it++)
        cout << it->first << " " << it->second << endl;
    return 0;
}