并查集解决食物链问题，p88

355 阅读 0 评论 0 点赞

#include <iostream>
    
    using namespace std;
    
    static const int MAX = 5000;
    static const int INF = (1 << 20);
    
    int par[MAX];	//父亲
    int Rank[MAX];
    
    //初始化n 个元素
    void initi(int n){
    	for(int i = 0; i < n; i++){
    		par[i] = i;
    		Rank[i] = 0;
    	}
    } 
    
    //查询树的根
    int Find(int x){
    	if(par[x] == x) return x;
    	else  return par[x] = Find(par[x]); 
    } 
    
    //合并x 和 y所属的集合
    void unite(int x, int y){
    	x = Find(x);
    	y = Find(y);
    	if(x == y) return;
    	
    	if(Rank[x] < Rank[y]) par[x] = y;
    	else{
    		par[y] = x;
    		if(Rank[x] == Rank[y]) Rank[x]++;
    	}
    } 
    
    //判断x 和 y 是否属于同一个集合
    bool same(int x, int y){
    	return Find(x) == Find(y);
    } 
    
    int N,K;
    int T[MAX], X[MAX], Y[MAX];
    
    int main(){
    	cin >> N >> K;
    	for(int i = 0; i < K; i++){
    		cin >> T[i] >> X[i] >> Y[i];
    	}	
    	//初始化并查集
    	//元素x, x + N, x + 2 * N 分别代表 x-A, x - B, x - C
    	initi(3 * N);
    	int ans = 0;		//不正确的信息数目
    	for(int i = 0; i < K; i++){
    		int t = T[i];
    		int x = X[i] - 1, y = Y[i] - 1;		//把输入变成0， ...N-1的范围
    		
    		//不正确的编号
    		if(x < 0 || x >= N || y < 0 || y >= N){
    			ans++;
    			continue;
    		} 
    		
    		if(t == 1){
    			//x 和 y 属于同一类的信息
    			if(same(x, y + N) || same(x, y + 2 * N)) ans++;
    			else{
    				unite(x, y);
    				unite(x + N, y + N);
    				unite(x + 2 * N, y + 2 * N); 
    			} 
    		}
    		else{
    			//x 吃 y 的信息
    			if(same(x, y) || same(x, y + 2 * N)){
    				ans++;
    			} 
    			else{
    				unite(x, y + N);
    				unite(x + N, y + 2 * N);
    				unite(x + 2 * N, y);
    			}
    		}
    	} 
    	
    	cout << ans << endl;
    	
    }

0.0分

1 人评分

本文分类：文章列表
浏览次数：355 次浏览
发布日期：2020-02-27 17:07:56
本文链接：https://blog.dotcpp.com/a/67085

C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程，并配有习题和答疑，点击了解：

一点编程也不会写的：零基础C语言学练课程

解决困扰你多年的C语言疑难杂症特性的C语言进阶课程

从零到写出一个爬虫的Python编程课程

只会语法写不出代码？手把手带你写100个编程真题的编程百练课程

信息学奥赛或C++选手的必学C++课程

蓝桥杯ACM、信息学奥赛的必学课程：算法竞赛课入门课程

手把手讲解近五年真题的蓝桥杯辅导课程

并查集解决食物链问题，p88

评论列表共有 0 条评论

发表评论取消回复

并查集解决食物链问题，p88

数位dp#2491: 信息学奥赛一本通T1587-Windy 数(C++)

点进来你会后悔的

简简单单的循环

简单的回文数

评论列表 共有 0 条评论

发表评论 取消回复

评论列表共有 0 条评论

发表评论取消回复