浙江大学软件学院2020年保研上机模拟练习 7-3 Partial School Ranking
程序员文章站
2022-05-19 20:58:35
...
并查集的使用时注意:
1. 合并两个结点是 F[sa] = sb 而不是 sb = F[sa],想一下含义。
2. 给每个结点赋予其自身为父节点时,要先判断它的父节点是不是0,也许已经有了。
我把照片里其他同学的成绩赋值为0,但是应该考虑到这张照片的配角也许是另外一张照片的主角,也就是该同学其实有成绩,所以只有在他的已有成绩不存在的情况下才能赋值为0。
AC代码
#include<cstdio>
#include<vector>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
using namespace std;
const int maxn = 10010;
int F[maxn] = {0};
int findS(int x){
int a = x;
while(x!=F[x]){
x = F[x];
}
while(a!=F[a]){
int z = a;
F[z] = x;
a = F[a];
}
return x;
}
void unite(int a,int b){
int sa = findS(a);
int sb = findS(b);
if(sa!=sb)F[sa] = sb;//注意点1
return;
}
map<int,int> idToG;
struct univ{
priority_queue<int,vector<int>,greater<int> > Q;
int sum = 0;
};
map<int,univ> idToU;
vector<univ> vi;
bool cmp(univ a,univ b){
if(a.sum!=b.sum)return a.sum>b.sum;
else if(a.Q.size()!=b.Q.size())return a.Q.size()<b.Q.size();
else return a.Q.top()<b.Q.top();
}
int main(){
int pN;//photo number
cin>>pN;
while(pN--){
int id,num,id2,grade;
cin>>id>>num;
if(F[id] == 0)F[id] = id;//注意点2
while(num--){
cin>>id2;
if(F[id2] == 0)F[id2] = id2;
if(!idToG[id2])idToG[id2] = 0;//注意点3
unite(id,id2);
}
cin>>grade;
idToG[id] = grade;
}
for(map<int,int>::iterator it = idToG.begin();it!=idToG.end();it++){
int id = it->first;
int grade = it->second;
int root = findS(id);
idToU[root].Q.push(id);
idToU[root].sum += grade;
}
for(map<int,univ>::iterator it = idToU.begin();it!=idToU.end();it++){
vi.push_back(it->second);
}
sort(vi.begin(),vi.end(),cmp);
printf("%d\n",vi.size());
for(int i=0;i<vi.size();i++){
printf("%04d %d %d\n",vi[i].Q.top(),vi[i].Q.size(),vi[i].sum);
}
return 0;
}