【前后缀优化建图+2-SAT】BZOJ3495(PA2010)[Riddle]题解

题目概述

有 n 个点， m 条边和 K 个国家（国家里的点已知）。每个国家只能选一个点作为首都，并且要保证最后所有边的两端至少有一个点是首都，问是否存在方案。

解题报告

每个点是首都或不是首都，只有两个状态，所以是2-SAT问题。m 条边的限制很容易转化，就是每个国家只能选一个点为首都比较奇怪。
其实这是典型的前后缀优化建图，这里以前缀优化建图为例：
首先我们先增加 n 个点，令 i 的新增节点为 i+n 。然后对于一个国家，假设有 w 个点，那么该国家中的第 i 个点（设为 A[i] ）的新增点 A[i]+n 表示该国家中1~ i 的点是否有被选的节点，即代表前缀 i 中是否有被选的节点。
那么我们可以得到以下关系式：
1. A[i−1]+n 选了， A[i]+n 必定选了； A[i]+n 没选， A[i−1]+n 必定没选（前缀之间的关系）。
2. A[i] 选了， A[i−1]+n 必定没选； A[i−1]+n 选了， A[i] 必定没选（一个国家只能有一个首都）。

后缀优化建图原理是一样的，只不过这道题并不需要后缀优化。
最后刷2-SAT判断是否存在解即可。

示例程序

#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=4000000,maxe=8000000;
int n,m,K;
int E,lnk[maxn+5],nxt[maxe+5],son[maxe+5];
int ti,dfn[maxn+5],low[maxn+5],tot,SCC[maxn+5],top,stk[maxn+5];
bool instk[maxn+5];
inline bool Eoln(char ch) {return ch==10||ch==13||ch==EOF;}
inline char readc()
{
static char buf[100000],*l=buf,*r=buf;
if (l==r) r=(l=buf)+fread(buf,1,100000,stdin);
if (l==r) return EOF; else return *l++;
}
inline int readi(int &x)
{
int tot=0,f=1;char ch=readc(),lst='+';
while ('9'<ch||ch<'0') {if (ch==EOF) return EOF;lst=ch;ch=readc();}
if (lst=='-') f=-f;
while ('0'<=ch&&ch<='9') tot=tot*10+ch-48,ch=readc();
return x=tot*f,Eoln(ch);
}
void Add(int x,int y) {son[++E]=y;nxt[E]=lnk[x];lnk[x]=E;}
void Tarjan(int x)
{
dfn[x]=low[x]=++ti;stk[++top]=x;instk[x]=true;
for (int j=lnk[x];j;j=nxt[j])
if (!dfn[son[j]]) Tarjan(son[j]),low[x]=min(low[x],low[son[j]]); else
if (instk[son[j]]) low[x]=min(low[x],dfn[son[j]]);
if (dfn[x]==low[x])
{
tot++;int y;
do y=stk[top--],instk[y]=false,SCC[y]=tot; while (y!=x);
}
}
bool Two_SAT()
{
for (int i=0;i<4*n;i++) if (!dfn[i]) Tarjan(i);
for (int i=0;i<4*n;i+=2)
if (SCC[i]==SCC[i^1]) return false;
return true;
}
int main()
{
freopen("program.in","r",stdin);
freopen("program.out","w",stdout);
readi(n);readi(m);readi(K);
for (int i=1,x,y;i<=m;i++)
readi(x),x--,readi(y),y--,Add(x<<1,y<<1^1),Add(y<<1,x<<1^1);
for (int i=0;i<n;i++) Add(i<<1^1,i+n<<1^1),Add(i+n<<1,i<<1);
for (int i=1;i<=K;i++)
{
int w,x,lst;readi(w);
for (int j=1;j<=w;j++,lst=x)
{
readi(x);x--;
if (j>1)
{
Add(x+n<<1,lst+n<<1);Add(lst+n<<1^1,x+n<<1^1);
Add(x<<1^1,lst+n<<1);Add(lst+n<<1^1,x<<1);
}
}
}
if (Two_SAT()) printf("TAKn"); else printf("NIEn");
return 0;
}

最后

以上就是激情高跟鞋为你收集整理的【前后缀优化建图+2-SAT】BZOJ3495(PA2010)[Riddle]题解的全部内容，希望文章能够帮你解决【前后缀优化建图+2-SAT】BZOJ3495(PA2010)[Riddle]题解所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。