为什么2-SAT做法会TLE10e5
查看原帖
为什么2-SAT做法会TLE10e5
752711
hateful_bug楼主2024/6/7 04:10

这段代码不应该O(n+m)吗 统计每个变量最终对应TFU或某个变量,用2-SAT做求对应点处于相同强连通分量数即为答案,但是T了3个点,有dalao能解答吗,感激不尽

#include<bits/stdc++.h>
using namespace std;
const int N=100005;
int rxcoffee,T,n,m,a[N],h[2*N],nx[2*N],b[2*N],tt,dfn[2*N],low[2*N],sjc,ans,zhan[2*N],top,cnt,c[2*N];
bool pd[2*N];
void zj(int x,int y)
{
	b[++tt]=y;
	nx[tt]=h[x];
	h[x]=tt;
}
void tarjan(int x)
{
	dfn[x]=low[x]=++sjc;
	pd[x]=true;zhan[++top]=x;
	for(int i=h[x];i;i=nx[i])
	{
		int y=b[i];
		if(!dfn[y])
		{
			tarjan(y);
			low[x]=min(low[x],low[y]);
		}
		else if(pd[y])
		low[x]=min(low[x],dfn[y]);
	}
	if(dfn[x]==low[x])
	{
		++cnt;
		int z;
		do
		{
			z=zhan[top--];
			pd[z]=false;
			c[z]=cnt;
		}while(x!=z);
	}
}
int main()
{
	scanf("%d%d",&rxcoffee,&T);
	while(T--)
	{
		scanf("%d%d",&n,&m);
		for(int i=1;i<=n;i++)
		a[i]=i;
		sjc=0;
		ans=0;
		tt=0;
		cnt=0;
		top=0;
		memset(dfn,0,sizeof(dfn));
		memset(pd,false,sizeof(pd));
		memset(h,0,sizeof(h));
		memset(nx,0,sizeof(nx));
		memset(b,0,sizeof(b));
		memset(c,0,sizeof(c));
		for(int i=1;i<=m;i++)
		{
			char s[2];
			int x,y;
			scanf("%s",s);
			if(s[0]=='+')
			{
				scanf("%d%d",&x,&y);
				a[x]=a[y];
			}
			else if(s[0]=='-')
			{
				scanf("%d%d",&x,&y);
				a[x]=-a[y];
			}
			else
			{
				scanf("%d",&x);
				if(s[0]=='T')
				a[x]=N;
				else if(s[0]=='F')
				a[x]=-N;
				else
				a[x]=0;
			}
		}
		for(int i=1;i<=n;i++)
		{
			if(a[i]==0)
			zj(i,i+n),zj(i+n,i);
			else if(a[i]==N)
			zj(i+n,i);
			else if(a[i]==-N)
			zj(i,i+n);
			else if(a[i]>0)
			zj(i,a[i]),zj(a[i],i),zj(i+n,a[i]+n),zj(a[i]+n,i+n);
			else
			zj(i,-a[i]+n),zj(-a[i]+n,i),zj(i+n,-a[i]),zj(-a[i],i+n);
		}
		for(int i=1;i<=n;i++)
		if(!dfn[i])
		tarjan(i);
		for(int i=1;i<=n;i++)
		if(c[i]==c[i+n])
		++ans;
		printf("%d\n",ans);
	}
	return 0;
}
2024/6/7 04:10
加载中...