欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

浙江大学软件学院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;
}

相关标签: 算法题 并查集