ninja (Spoj-SOPARADE)

题目大意

有n个位置，每个位置有一个标识，范围为1到4，限制相邻两个位置的差的绝对值至少为2。同时还给出了m个限制，每个限制选定k个位置，要求这k个位置上的标识互不相同。请你输出是否存在合法的方案使得所有位置上的标识都满足限制。 n,m<=100000

2-SAT

奇数位置和偶数位置上的标识肯定是不同的，因为相邻两个位置的差的绝对值至少为2。 当然，不止这点性质。 位置1上的标识如果为1或2，位置2的标识只能为3或4，位置3的标识只能为1或2，位置4的标识又只能为3或4。。。 事实上，如果某个奇数位置上的标识为1或2，则所有奇数位置上的标识只能为1或2，所有偶数位置的标识只能为3或4。反过来，如果某个奇数位置上的标识为3或4，则所有奇数位置上的标识只能为3或4，所有偶数位置的标识只能为1或2。由于只考虑是否存在合法方案，所以这两种情况在我们眼里是等价的，考虑其中一种即可。 那么对于一个位置，我们拆成两个点，一个表示取真(对于奇数位置表示标识取1，对于偶数位置表示标识取4)，一个表示取假(对于奇数位置表示标识取3，对于偶数位置表示标识取2) 那么这就是个经典的2-SAT的问题了。 对于限制相邻两个位置的差的绝对值至少为2，相当于限制相邻两个位置至少一个取真。 那么可以通过连边(有向边)来表示限制。 例如两个位置i和j，至少一个为真，设i表示i取真的点，i+n表示i取假的点，则这样连边 i+n—>j j+n—>i 这样i取假时，j必为真；j取假时，i必为真。 另m个限制，我们可以类似的连边，有一个trick，k的取值最大为4(显然。。。) 同时奇偶位置可以分开连边，因为奇数位置和偶数位置上的标识肯定是不同的。 然后2-SAT的问题有多种算法，比如tarjan缩环之类的(身为蒟蒻并不会) 还有一种朴素的O(nm)的做法，对于所有未确定的点，取真dfs一遍，若不符要求，再取假dfs一遍，实际应用中复杂度一般都达不到理论复杂度(比如说这题)，而且该算法有一个很重要的用处：求字典序最小的解！(虽然和这题没啥关系)

代码

#include<cstring> #include<cstdio> #include<algorithm> #include<cmath> #define fo(i,a,b) for(i=a;i<=b;i++) using namespace std; const int maxn=100000+5; int i,j,n,t,l,m,num,cnt; int f1[5],f2[5],k[maxn*2],g[maxn*10],next[maxn*10],q[maxn*2],ba[maxn*2]; bool bz[maxn*2]; void add(int x,int y){ next[++num]=k[x],k[x]=num,g[num]=y; } void ad(int x,int y){ add(x,y+n);add(x+n,y);add(y+n,x);add(y,x+n); } int re(int x){ if (x<n) return x+n;else return x-n; } bool dfs(int x){ if (bz[x]||(ba[x]==cnt)) return 1; q[++num]=x; ba[x]=cnt;int y=re(x);if (bz[y]||(ba[y]==cnt)) return 0; int i=k[x]; while (i){ if (!dfs(g[i])) return 0; i=next[i]; } return 1; } bool df(int x){ num=0; cnt++; if (dfs(x)) { int i;fo(i,1,num) bz[q[i]]=1; return 1; }return 0; } int main(){ scanf("%d",&t); fo(l,1,t){ scanf("%d%d",&n,&m);num=0; memset(k,0,sizeof(k)); memset(bz,0,sizeof(bz)); memset(ba,0,sizeof(ba));cnt=0; bool b=1; fo(i,1,n) {if (i<n) add(i+n,i+1);if (i>1) add(i+n,i-1);} fo(i,1,m){ int w,t1=0,t2=0; scanf("%d",&w); fo(j,1,w) { int y;scanf("%d",&y); if (y%2) f1[++t1]=y;else f2[++t2]=y; }if ((t1>2)||(t2>2)) b=0; if (!b) continue; if (t1==2) ad(f1[1],f1[2]); if (t2==2) ad(f2[1],f2[2]); } if (!b){printf("rejected\n");continue;} fo(i,1,n) if (!bz[i]&&!bz[i+n]){ b=0; if (df(i)) b=1;else if (df(i+n)) b=1; if (!b) break; } if (!b) printf("rejected\n");else printf("approved\n"); } }