本文主要是介绍PAT A1034（附测试点2、3、5分析），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
1.思路
两个map分别对应着string->int和int->string的功能
图的dfs遍历
2.测试点注意
测试点2：答案错误（应该是没有考虑题目中要求的最后输出的每行要求按照帮派头领名称的字典序从小到大，需要加入按名称字典序排序的操作）
测试点3：段错误（应该是数组开小了，注意在无向图中，数组尽量都开到2*N，N为题目给出的最多结点数）
测试点5：答案错误（题目中似乎没有给出明确的要求，应当是当一个帮派内部有两个结点的权值相同时，也需要按照字典序大小来选择小的那一个）
code
#include<bits/stdc++.h>
using std::cin;
using std::cout;
using std::endl;
using std::string;
using std::unordered_map;
int n,k,boss,cnt,ans,people;
int value[2005];
bool visit[2005];
int head[2002];
int flag[2001][2001];
unordered_map<string,int> mp;
unordered_map<int,string> reverse_mp;//笔者使用的unordered_map，操作和效果与map一样，不影响
struct node
{int point;//存储当前帮派的老大int human;//存储当前帮派的人数
}a[4000];
struct EDGE
{int next,to,val;
}edge[2002];
bool cmp(node b,node c)
{string str1=reverse_mp[b.point];string str2=reverse_mp[c.point];return str1<str2;
}
inline void add(int a,int b,int c)
{if(!flag[a][b]){edge[++cnt].to=b;edge[cnt].next=head[a];edge[cnt].val=c;head[a]=cnt;flag[a][b]=cnt;}else{int temp=flag[a][b];edge[temp].val+=c;}
}
void dfs(int root)
{people++;visit[root]=true;if(value[root]>value[boss]){boss=root;}if(value[root]==value[boss]&&reverse_mp[root]<reverse_mp[boss]){ boss=root;}for(int i=head[root];i;i=edge[i].next){int v=edge[i].to;ans+=edge[i].val;if(visit[v]==false) dfs(v);}
}
signed main(void)
{scanf("%d%d",&n,&k);string str1,str2;int temp,num=0,sum=0;for(int i=1;i<=n;i++){cin>>str1>>str2>>temp;unordered_map<string,int>::iterator it1=mp.find(str1);unordered_map<string,int>::iterator it2=mp.find(str2);if(it1==mp.end()) {mp[str1]=num++;reverse_mp[num-1]=str1;}if(it2==mp.end()) {mp[str2]=num++;reverse_mp[num-1]=str2;}add(mp[str1],mp[str2],temp);add(mp[str2],mp[str1],temp);value[mp[str1]]+=temp;value[mp[str2]]+=temp;}for(int i=0;i<num;i++){if(visit[i]==false) {ans=0;boss=i;people=0;dfs(i);
// cout<<ans<<" "<<people<<endl;if(people>2&&ans>2*k)//因为边是双向边，在加的时候会重复加一次{sum++;a[sum].point=boss;a[sum].human=people;}}}std::sort(a+1,a+1+sum,cmp);printf("%d\n",sum);for(int i=1;i<=sum;i++){cout<<reverse_mp[a[i].point];printf(" %d\n",a[i].human);}return 0;
}
这篇关于PAT A1034（附测试点2、3、5分析）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
