PAT_A1034
PAT甲级1034.
目录
A1034
题目
样例
样例1
输入:
8 59
AAA BBB 10
BBB AAA 20
AAA CCC 40
DDD EEE 5
EEE DDD 70
FFF GGG 30
GGG HHH 20
HHH FFF 10
输出:
2
AAA 3
GGG 3
样例2
输入:
8 70
AAA BBB 10
BBB AAA 20
AAA CCC 40
DDD EEE 5
EEE DDD 70
FFF GGG 30
GGG HHH 20
HHH FFF 10
输出:
0
思路和坑点
此题有两种思路，一种是使用图的dfs算法进行处理，另一种是使用并查集的方法实现，这里对并查集实现的方法作详细的介绍，dfs算法仅给出AC代码。
把每一个人当作一个独立的个体，它既是一个并查集中的元素，也是一个犯罪团伙，用一个结构体记录作为个体以及作为一个团伙的相关信息，根据通话记录进行合并。
由于id都是字母，使用map映射分配结构体数组的下标，同时按照下标成对的存放通话记录，比如i和j通过话，这该记录为i*10000+j来保存（考虑到最多有2000人，因此使用10000来作为进率。这样的记录通过/和%运算（对10000执行）分离两个通话着的下标。
根据通话记录进行并查集的合并，并更新并查集中的信息，最后对每一个进行筛选，如果符合要求则输出。
AC代码 （并查集实现）
#include<bits/stdc++.h>
using namespace std;
map<string,int> mp; //id对应的下标映射
typedef struct node{ //每一个人对应的个人结构体，同时认为每个人是一个并查集，也是一个单独的团伙，
string id; //个人的id
int w,fa,maxi,total; //通话权重，并查集的father，该团伙中最大权重的id对应的下标（合并时用于更新团伙），团伙中的总权重（用于判定）
node(){ //初始化fa=-1表示该并查集只有一个人，总权重为0
fa=-1; w=total=0;
}
}Node;
Node v[2002]; //1000条信息，所以最多2000个人
int find_fa(int x){ //查找并查集的祖先
while(v[x].fa>=0){
x=v[x].fa;
}
return x;
}
void Union(int i,int j){ //并查集的合并
int fi=find_fa(i),fj=find_fa(j);
if(fi==fj) return; //如果两个人在同一个并查集中，不需要合并
if(v[fi].fa>v[fj].fa) //把小的合并到大的中，判断大小，为了代码统一，做适当的交换
swap(fi,fj); //并查集的根指向一个负数，数的绝对值代表并查集中元素个数
v[fi].fa+=v[fj].fa; //更新大小
v[fj].fa=fi; //合并
v[fi].total+=v[fj].total; //更新总权值
int p=v[fi].maxi,q=v[fj].maxi; //更新最大权值的id下标
v[fi].maxi=v[p].w>v[q].w?p:q;
}
int main(void){
#ifdef ONLINE_JUDGE
#else
freopen("1.txt","r",stdin);
#endif
int n,k,cnt=0;
scanf("%d%d",&n,&k);
k*=2; //合并更新总权值的时候计算会重复，所以筛选限度×2
vector<int> data(n);
for(int i=0;i<n;i++){
string a,b;
int c;
cin>>a>>b>>c;
if(mp.find(a)==mp.end()) mp[a]=cnt++; //分配下标
if(mp.find(b)==mp.end()) mp[b]=cnt++;
int ia=mp[a],ib=mp[b];
data[i]=ia*10000+ib; //将两个人的通话记录保存一下用于合并并查集
v[ia].w+=c; v[ia].id=a; v[ia].maxi=ia; v[ia].total+=c; //更新权重
v[ib].w+=c; v[ib].id=b; v[ib].maxi=ib; v[ib].total+=c;
}
for(int i=0;i<n;i++){
int a=data[i]/10000,b=data[i]%10000;
Union(a,b); //根据通话记录进行合并
}
map<string,int> out; //结果存放
for(int i=0;i<cnt;i++){ //按要求筛查
if(v[i].fa<-2&&v[i].total>k){ //如果团伙人数超过两人，并且超过限度
int k=v[i].maxi;
out[v[k].id]=-v[i].fa;
}
}
printf("%d\n",out.size()); //输出结果
for(auto it=out.begin();it!=out.end();it++){
cout<<it->first<<' '<<it->second<<'\n';
}
return 0;
}
AC代码 （图的dfs算法实现）
#include<bits/stdc++.h>
using namespace std;
const int MAXV=2010;
const int INF=1000000000;
int G[MAXV][MAXV]={0},weight[MAXV]={0};
int n,k,numP=0;
bool vis[MAXV]={false};
map<int,string> int_str;
map<string,int> str_int;
map<string,int> gang;
void DFS(int u,int &head,int &numM,int &total);
void DFSTrave();
int change(string str);
int main(void)
{
int w;
string s1,s2;
cin>>n>>k;
for(int i=0;i<n;i++){
cin>>s1>>s2>>w;
int id1=change(s1);
int id2=change(s2);
weight[id1]+=w;
weight[id2]+=w;
G[id1][id2]+=w;
G[id2][id1]+=w;
}
DFSTrave();
cout<<gang.size()<<'\n';
for(auto it=gang.begin();it!=gang.end();it++){
cout<<it->first<<' '<<it->second<<'\n';
}
return 0;
}
int change(string str)
{
if(str_int.find(str)!=str_int.end()) return str_int[str];
else{
str_int[str]=numP;
int_str[numP]=str;
return numP++; //先return，在numP++，因为到括号程序才算结束
}
}
void DFS(int u,int &head,int &numM,int &total)
{
numM++; //该组成员人数加一
vis[u]=true;
if(weight[u]>weight[head]) head=u;
for(int i=0;i<numP;i++){
if(G[u][i]>0){
total+=G[u][i];
G[u][i]=G[i][u]=0;
if(vis[i]==false){
DFS(i,head,numM,total);
}
}
}
}
void DFSTrave()
{
for(int i=0;i<numP;i++){
if(vis[i]==false){
int head=i,numM=0,total=0;
DFS(i,head,numM,total);
if(numM>2&&total>k){
gang[int_str[head]]=numM;
}
}
}
}