SPOJ SOPARADE

题目大意

有 n 个人，每个人需要有一个[1,4]的标识符。 其中相邻两个人的标识符绝对值一定要大于等于2。 还有 m 个条件，每个条件给出的人的标识符必须不同。 问是否存在。

n,m≤100000

解题思路

首先可以发现奇数位只可能是1或2，偶数位只可能是3或4。 那么把每个位置拆成两个点，这就变成了2-sat. Tarjan判断2-sat是否存在矛盾即可。

参考代码

#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #include<vector> #define fo(i,a,b) for(int i=a;i<=b;i++) #define fd(i,a,b) for(int i=a;i>=b;i--) #define maxn 200005 #define mem(a,b) memset(a,b,sizeof(a)) #define pb(a) push_back(a) #define min(a,b) (((a) < (b)) ? a : b) using namespace std; int dfn[maxn],low[maxn],tim; int sta[maxn],stin[maxn]; int bel[maxn],totb; int head[maxn],t[maxn * 20],next[maxn * 20],sum; int T,n,m; vector<int> p[2]; int NOT(int x){ return x<=n ? x+n : x-n; } void ins(int x,int y){ t[++sum]=y; next[sum]=head[x]; head[x]=sum; } void tarjan(int x){ stin[x]=1; sta[++sta[0]]=x; dfn[x]=low[x]=++tim; for(int tmp=head[x];tmp;tmp=next[tmp]) { if (dfn[t[tmp]]==0) { tarjan(t[tmp]); low[x]=min(low[x],low[t[tmp]]); } else if (stin[t[tmp]]) low[x]=min(low[x],dfn[t[tmp]]); } if (low[x]==dfn[x]) { totb++; while (sta[sta[0]]!=x) { int tmp=sta[sta[0]]; stin[tmp]=0; sta[0]--; bel[tmp]=totb; } int tmp=sta[sta[0]]; stin[tmp]=0; sta[0]--; bel[tmp]=totb; } } inline int Read(){ int ret=0,ff=1; char c=getchar(); while (c<'0' || c>'9') { if (c=='-') ff=-1; c=getchar(); } while (c>='0' && c<='9') { ret=ret*10+c-'0'; c=getchar(); } return ret; } int main(){ T=Read(); while (T--) { mem(head,0); sum=0; mem(dfn,0); mem(low,0); mem(bel,0); totb=0; tim=0; sta[0]=0; n=Read(); m=Read(); fo(i,1,n) { if (i<n) ins(NOT(i),i+1); if (i>1) ins(NOT(i),i-1); } bool ok=0; fo(i,1,m) { int x; x=Read(); p[0].clear(); p[1].clear(); fo(j,1,x) { int y=Read(); p[y % 2].pb(y); } if (p[0].size()>2 || p[1].size()>2) ok=1; if (p[0].size()==2) { ins(p[0][0],NOT(p[0][1])); ins(NOT(p[0][0]),p[0][1]); } if (p[1].size()==2) { ins(p[1][0],NOT(p[1][1])); ins(NOT(p[1][0]),p[1][1]); } } bool ans=1; fo(i,1,n) { if (dfn[i]==0) tarjan(i); if (dfn[i+n]==0) tarjan(i+n); if (bel[i]==bel[i+n]) { ans=0; break; } } puts(ans ? "approved" : "rejected"); } return 0; }