noip t2思路求指正
  • 板块学术版
  • 楼主hdkk
  • 当前回复0
  • 已保存回复0
  • 发布时间2023/11/19 21:43
  • 上次更新2023/11/20 12:34:06
查看原帖
noip t2思路求指正
728778
hdkk楼主2023/11/19 21:43

我的思路是处理最后赋值的情况,被赋值的点和赋值的点两个点值相同,用并查集合并,如果一个变量的正点和负点在一个集合或者U在这个集合,这个集合的点值是U,洛谷上只有60分,请问是我思路假了还是代码假了?

#include<bits/stdc++.h> 
using namespace std;
int fa[4000005],ed[4000005],vis[4000005],n,m,c,tt;
int findd(int x)
{
	if(fa[x]!=x)
		fa[x]=findd(fa[x]);
	return fa[x];
 } 
int main()
{
	cin>>c>>tt;
	while(tt--)
	{
		cin>>n>>m;
		for(int i=1;i<=2*n+3;i++)
		{
			fa[i]=i;
			ed[i]=i;
			vis[i]=0;
		}
		int x,y,t=2*n+1,f=2*n+2,u=2*n+3;
		char opt;
		for(int i=1;i<=m;i++)
		{
			cin>>opt;
			if(opt=='+')
			{
				cin>>x>>y;
				ed[x]=ed[y];
				ed[x+n]=ed[y+n];
			}
			if(opt=='-')
			{
				cin>>x>>y;
				ed[x+n]=ed[y];
				ed[x]=ed[y+n];
			}
			if(opt=='T')
			{
				cin>>x;
				ed[x]=ed[t];
				ed[x+n]=ed[f];
			}
			if(opt=='F')
			{
				cin>>x;
				ed[x+n]=ed[t];
				ed[x]=ed[f];
			}
			if(opt=='U')
			{
				cin>>x;
				ed[x]=ed[x+n]=ed[u];
			}
		}
		for(int i=1;i<=2*n+3;i++)
		{
			int r1=findd(i),r2=findd(ed[i]);
			if(r1!=r2)
				fa[r1]=r2;
		}
		for(int i=1;i<=n;i++)
		{
			if(findd(i==findd(i+n))
				vis[findd(i)]=1;
		}
		int ans=0;
		vis[findd(u)]=1;
		for(int i=1;i<=n;i++)
		{
			if(vis[findd(i)])
				ans++;
		}
		cout<<ans<<endl;
	} 
    
    return 0;
}
2023/11/19 21:43
加载中...