2-SAT 74pts球跳
查看原帖
2-SAT 74pts球跳
1285596
fall_asleep楼主2025/7/22 15:25
#include<bits/stdc++.h>
using namespace std;
const int N=5e3+5;
int n;
int k,s;
bool vis[N][N];
vector<int> edge[N<<1];
int dfn[N<<1],low[N<<1],cnt,from[N],num;
bool ins[N<<1];
stack<int> st;
void tarjan(int u)
{
	dfn[u]=low[u]=++cnt;
	ins[u]=1;
	st.push(u);
	for(auto v:edge[u])
	{
		if(!dfn[v])
		{
			tarjan(v);
			low[u]=min(low[u],low[v]);
		}
		if(ins[v]) low[u]=min(low[u],dfn[v]);
	}
	if(dfn[u]==low[u])
	{
		++num;
		while(st.top()!=u)
		{
			ins[st.top()]=0;
			from[st.top()]=num;
			st.pop();
		}
		ins[u]=0;from[u]=num;
		st.pop();
	}
}
vector<int> ans0,ans1;
int ans=0;
int ans00=0,kff[N];
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>k;
		for(int j=1;j<=k;j++)
		{
			cin>>s;
			vis[s][i]=vis[i][s]=1;
		}
	}
	for(int i=1;i<=n;i++)
		for(int j=i+1;j<=n;j++)
		{
			int u0=i,u1=i+n,v0=j,v1=j+n;
			if(vis[i][j])
				edge[u0].push_back(v1),edge[v0].push_back(u1);
			else edge[u1].push_back(v0),edge[v1].push_back(u0);
		}
	for(int i=1;i<=2*n;i++)
		if(!dfn[i])
			tarjan(i);
	for(int i=1;i<=n;i++)
	{
		if(from[i]==from[i+n])
		{
			cout<<0;
			return 0;
		}
		if(from[i]<from[i+n]) ans0.push_back(i)/*,cout<<0*/;//no
		else ans1.push_back(i)/*,cout<<1*/;//yes
	}
	for(auto u:ans0)
	{
		bool flag=0;
		int ks=0;
		for(auto v:ans1)
		{
			if(!vis[u][v] and !flag)
				flag=1,ks=v;
			else if(flag and !vis[u][v])
			{
				flag=0;
				break;
			}
		}
		if(!flag and !ks) ans++,ans00++;//都认识
		else if(flag and ks) kff[ks]++;//只有一个不认识
	}//仅仅不认识 ks
	for(auto u:ans1)
	{
		bool flag=0;
		int ks=0;
		for(auto v:ans0)
		{
			if(vis[u][v] and !flag)
				flag=1,ks=v;
			else if(flag and vis[u][v])
			{
				flag=0;
				break;
			}
		}
		if(!flag and !ks) ans++,ans+=ans00+kff[u];//都不认识
		else if(flag and ks)
			ans+=kff[u];
	}
	cout<<ans+1<<'\n';
	return 0;
}
2025/7/22 15:25
加载中...