社区讨论

为什么用了快读还是90分

P2024[NOI2001] 食物链参与者 4已保存回复 4

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
4 条
当前快照
1 份
快照标识符
@lo90ps7i
此快照首次捕获于
2023/10/28 03:40
2 年前
此快照最后确认于
2023/10/28 03:40
2 年前
查看原帖
CPP
cpp
//种类并查集
//种类并查集求的并非具体种类,而是关系! 
#include<bits/stdc++.h>
using namespace std;
const int N=100010;
int n,m,a,b,c,ans=0,cnt=0;
int fa[N];
map <string,int> mp; 

inline int read()
{
	char c = getchar(); int n = 0;
	while (c < '0' || c > '9') { c = getchar(); }
	while (c >= '0' && c <= '9') { n = (n << 1) + (n << 3) + (c & 15); c = getchar(); }
	return n;
}

int find(int x)//找x的根节点 
{
	if(x == fa[x])  return x;
	else  return   fa[x] = find(fa[x]);
}

void merge(int x,int y)
{
	fa[find(x)] = find(y);//找到y的根节点和x的根节点,并把它连起来 
}


int main()
{
//	cin>>n>>m;
    n=read();
    m=read();
	for(int i=1;i<=3*n;i++)
	    fa[i]=i;
	while(m--)
	{
//		cin>>a>>b>>c;
        a=read();
        b=read();        
		c=read();		 
        
		if(b>n || c>n)//不要忘了特判编号大于 n 的情况!
		{
			ans++;
			continue;
		}
		
		if(a==1)
		{
			//错误点1:如果直接判,那么本来每个元素的根都是他自己,所以ans++永远成立
			 
//			if((find(b) == find(c)) || (find(b+n) == find(c+n)) || (find(b+2*n) == find(c+2*n))) 
//			{
//			    merge(b,c);
//			    merge(b+n,c+n);
//			    merge(b+2*n,c+2*n);
//			}
//			else ans++;
		    if(find(b)==find(c+n) || find(b) ==find(c+2*n))			
		        ans++;
		    else
		    {
		    	merge(b,c);
				merge(b+n,c+n);
				merge(b+2*n,c+2*n);
			}
		} 
		if(a==2)
		{
//			if((find(b) == find(c+n)) || (find(b+n) == find(c+2*n)) || (find(b+2*n) == find(c)))
//			{
//			    merge(b,c+n);
//			    merge(b+n,c+2*n);
//			    merge(b+2*n,c);
//			}
//			else ans++;

			//错误点2:如果直接判,那么本来每个元素的根都是他自己,所以ans++永远成立
            if(find(b) == find(c) ||find(b) == find(c+2*n))  ans++;
            else
            {
        		merge(b,c+n);
        		merge(b+n,c+2*n);
        		merge(b+2*n,c);
        		continue;
			}
		}
//		cout<<cnt<<" "<<"ans="<<ans<<endl;
	} 
	cout<<ans<<endl;
	return 0;
}

回复

4 条回复,欢迎继续交流。

正在加载回复...