B1034 Head of a Gang (30分)

//用邻接矩阵存储图时有注意点

• 1.因为题目要求：通话记录N<=1000，所以当每次通话都是不同两个人时，就有2000个人了
• 2.AAA~ZZZ最多有26 * 26 * 26种，直接转成数字，邻接矩阵数组就会段错误，所以转成数字采用计数法，一个英文对应到一个数字
• 也可以采用map<string,vector<node> >来存。

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <cmath>
#include <math.h>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <stack>
#define lowbit(i)((i)&(-i))
using namespace std;
typedef long long ll;
const int MAX=2010;
const int INF=0x3f3f3f3f;
const int MOD=1000000007;
const int SQR=632;//633块，632个
int n,k,sum,num,maxindex;
int idnum=1;
int G[2010][2010];
int weight[2010];
int book[2010];
map<string,int>stringtoint,ans;
map<int,string>inttostring;
int change(string s)
{
    if(stringtoint[s]==0)
    {
        stringtoint[s]=idnum;
        inttostring[idnum]=s;
        return idnum++;
    }
    else
        return stringtoint[s];
}
void dfs(int x)
{
    book[x]=1;
    num++;
    if(weight[x]>weight[maxindex])
    {
        maxindex=x;
    }
    for(int i=1;i<idnum;i++)
    {
        if(G[x][i]!=0)
        {
            sum+=G[x][i];
            G[x][i]=G[i][x]=0;
            if(book[i]==0)
            {
                dfs(i);
            }
        }
    }

}
int main()
{
    scanf("%d%d",&n,&k);
    for(int i=0;i<n;i++)
    {
        string x,y;
        int d;
        cin>>x>>y;
        int a=change(x);
        int b=change(y);
        scanf("%d",&d);
        weight[a]+=d;
        weight[b]+=d;
        G[a][b]+=d;
        G[b][a]+=d;
    }
    memset(book,0,sizeof(book));
    for(int i=1;i<idnum;i++)
    {
        sum=0,num=0;
        maxindex=i;
        if(book[i]==0)
        {
            dfs(i);
        }
        if(sum>k&&num>2)
        {
            ans[inttostring[maxindex]]=num;
        }
    }
    cout<<ans.size()<<endl;
    for(map<string,int>::iterator it=ans.begin();it!=ans.end();it++)
    {
        cout<<it->first<<" "<<it->second<<endl;
    }
   return 0;
}

或者

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <cmath>
#include <math.h>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <stack>
#define lowbit(i)((i)&(-i))
using namespace std;
typedef long long ll;
const int MAX=2010;
const int INF=0x3f3f3f3f;
const int MOD=1000000007;
const int SQR=632;//633块，632个
int n,k,sum,num,maxindex;
struct node
{
    string id;
    int w;
};
map<string,vector<node> >G;
map<string,int>idtoweight,book,ans;
void dfs(string s,string &maxstring)
{
    book[s]=1;
    num++;
    if(idtoweight[s]>maxindex)
    {
        maxindex=idtoweight[s];
        maxstring=s;
    }
    for(int i=0;i<G[s].size();i++)
    {
        sum+=G[s][i].w;
        if(book[G[s][i].id]==0)
        {
            dfs(G[s][i].id,maxstring);
        }
    }
}
int main()
{
    scanf("%d%d",&n,&k);
    for(int i=0;i<n;i++)
    {
        string x,y;
        int weight;
        cin>>x>>y;
        scanf("%d",&weight);
        G[x].push_back({y,weight});
        G[y].push_back({x,weight});
        idtoweight[x]+=weight;
        idtoweight[y]+=weight;
    }
    for(map<string,vector<node> >::iterator it=G.begin();it!=G.end();it++)
    {
        if(book[it->first]==0)
        {
            num=0,sum=0;
            maxindex=0;
            string s;
            dfs(it->first,s);
            if(num>=3&&sum/2>k)
            {
                ans[s]=num;
            }
        }
    }
    cout<<ans.size()<<endl;
    for(map<string,int>::iterator it=ans.begin();it!=ans.end();it++)
    {
        cout<<it->first<<" "<<it->second<<endl;
    }
   return 0;
}