魏（2-sat）（前缀建边优化）

【题目描述】
魏国有n个城镇被分成了k个郡，有m条连接城镇的无向边。
曹操要求给每个郡选择一个城镇作为首都，满足每条边至少有一个端点是首都。
【输入格式】
第一行有三个整数，城镇数n（1<=n<=10^{6），边数m（0<=m<=10}6），郡数k（1<=k<=n）。
接下来m行，每行有两个整数ai和bi（ai≠bi），表示有一条无向边连接城镇ai和bi。
接下来k行，第j行以一个整数wj开头，后面是wj个整数，表示第j个郡包含的城镇。
【输出格式】
若有解输出TAK，否则输出NIE。
【输入样例】
6 5 2
1 2
3 1
1 4
5 2
6 2
3 3 4 2
3 1 6 5
【输出样例】
TAK

可以发现是个裸的2-sat，连边用前缀优化一下就行了
UPD：
这个2-sat不裸。。。。。。里面前缀优化的时候似乎是全程$xor$所以才可以$2-sat$的。

#include<bits/stdc++.h>
#define maxn 4000006
using namespace std;
namespace IO{
#define BUF_SIZE 100000
#define OUT_SIZE 100000
#define ll long long
//fread->read
bool IOerror=0;
inline char nc(){
static char buf[BUF_SIZE],*p1=buf+BUF_SIZE,*pend=buf+BUF_SIZE;
if (p1==pend){
p1=buf; pend=buf+fread(buf,1,BUF_SIZE,stdin);
if (pend==p1){IOerror=1;return -1;}
//{printf("IO error!n");system("pause");for (;;);exit(0);}
}
return *p1++;
}
inline bool blank(char ch){return ch==' '||ch=='n'||ch=='r'||ch=='t';}
inline void read(int &x){
bool sign=0; char ch=nc(); x=0;
for (;blank(ch);ch=nc());
if (IOerror)return;
if (ch=='-')sign=1,ch=nc();
for (;ch>='0'&&ch<='9';ch=nc())x=x*10+ch-'0';
if (sign)x=-x;
}
inline void read(ll &x){
bool sign=0; char ch=nc(); x=0;
for (;blank(ch);ch=nc());
if (IOerror)return;
if (ch=='-')sign=1,ch=nc();
for (;ch>='0'&&ch<='9';ch=nc())x=x*10+ch-'0';
if (sign)x=-x;
}
inline void read(double &x){
bool sign=0; char ch=nc(); x=0;
for (;blank(ch);ch=nc());
if (IOerror)return;
if (ch=='-')sign=1,ch=nc();
for (;ch>='0'&&ch<='9';ch=nc())x=x*10+ch-'0';
if (ch=='.'){
double tmp=1; ch=nc();
for (;ch>='0'&&ch<='9';ch=nc())tmp/=10.0,x+=tmp*(ch-'0');
}
if (sign)x=-x;
}
inline void read(char *s){
char ch=nc();
for (;blank(ch);ch=nc());
if (IOerror)return;
for (;!blank(ch)&&!IOerror;ch=nc())*s++=ch;
*s=0;
}
inline void read(char &c){
for (c=nc();blank(c);c=nc());
if (IOerror){c=-1;return;}
}
//fwrite->write
struct Ostream_fwrite{
char *buf,*p1,*pend;
Ostream_fwrite(){buf=new char[BUF_SIZE];p1=buf;pend=buf+BUF_SIZE;}
void out(char ch){
if (p1==pend){
fwrite(buf,1,BUF_SIZE,stdout);p1=buf;
}
*p1++=ch;
}
void print(int x){
static char s[15],*s1;s1=s;
if (!x)*s1++='0';if (x<0)out('-'),x=-x;
while(x)*s1++=x%10+'0',x/=10;
while(s1--!=s)out(*s1);
}
void println(int x){
static char s[15],*s1;s1=s;
if (!x)*s1++='0';if (x<0)out('-'),x=-x;
while(x)*s1++=x%10+'0',x/=10;
while(s1--!=s)out(*s1); out('n');
}
void print(ll x){
static char s[25],*s1;s1=s;
if (!x)*s1++='0';if (x<0)out('-'),x=-x;
while(x)*s1++=x%10+'0',x/=10;
while(s1--!=s)out(*s1);
}
void println(ll x){
static char s[25],*s1;s1=s;
if (!x)*s1++='0';if (x<0)out('-'),x=-x;
while(x)*s1++=x%10+'0',x/=10;
while(s1--!=s)out(*s1); out('n');
}
void print(double x,int y){
static ll mul[]={1,10,100,1000,10000,100000,1000000,10000000,100000000,
1000000000,10000000000LL,100000000000LL,1000000000000LL,10000000000000LL,
100000000000000LL,1000000000000000LL,10000000000000000LL,100000000000000000LL};
if (x<-1e-12)out('-'),x=-x;x*=mul[y];
ll x1=(ll)floor(x); if (x-floor(x)>=0.5)++x1;
ll x2=x1/mul[y],x3=x1-x2*mul[y]; print(x2);
if (y>0){out('.'); for (size_t i=1;i<y&&x3*mul[i]<mul[y];out('0'),++i); print(x3);}
}
void println(double x,int y){print(x,y);out('n');}
void print(char *s){while (*s)out(*s++);}
void println(char *s){while (*s)out(*s++);out('n');}
void flush(){if (p1!=buf){fwrite(buf,1,p1-buf,stdout);p1=buf;}}
~Ostream_fwrite(){flush();}
}Ostream;
inline void print(int x){Ostream.print(x);}
inline void println(int x){Ostream.println(x);}
inline void print(char x){Ostream.out(x);}
inline void println(char x){Ostream.out(x);Ostream.out('n');}
inline void print(ll x){Ostream.print(x);}
inline void println(ll x){Ostream.println(x);}
inline void print(double x,int y){Ostream.print(x,y);}
inline void println(double x,int y){Ostream.println(x,y);}
inline void print(char *s){Ostream.print(s);}
inline void println(char *s){Ostream.println(s);}
inline void println(){Ostream.out('n');}
inline void flush(){Ostream.flush();}
#undef ll
#undef OUT_SIZE
#undef BUF_SIZE
};
using namespace IO;
int n,m,k,cnt_p;
int info[maxn],Prev[maxn*8],to[maxn*8],cnt_e;
inline void Node(const int &u,const int &v){ Prev[++cnt_e]=info[u],info[u]=cnt_e,to[cnt_e]=v; }
int dfn[maxn],low[maxn],tot,c[maxn],scc,q[maxn],tp;
void dfs(int now)
{
dfn[now] = low[now] = ++tot;
q[tp++] = now;
for(register int i=info[now];i;i=Prev[i])
if(!dfn[to[i]]) dfs(to[i]) , low[now] = min(low[now] , low[to[i]]);
else if(!c[to[i]]) low[now] = min(low[now] , dfn[to[i]]);
if(dfn[now] == low[now])
{
register int tmp = -1;scc++;
for(;tmp!=now;)
c[tmp = q[--tp]] = scc;
}
}
int main()
{
read(n),read(m),read(k);
for(register int i=1,u,v;i<=m;i++) read(u),read(v),Node(u<<1|1,v<<1),Node(v<<1|1,u<<1);
cnt_p=n;
for(register int i=1;i<=k;i++)
{
int N , tmp = -1;
read(N);
for(register int u;N--;)
{
read(u);
cnt_p++;
if(tmp!=-1)
{
Node(tmp<<1 , cnt_p<<1) , Node(tmp<<1 ,
u<<1|1);
Node(cnt_p<<1|1,tmp<<1|1),Node(cnt_p<<1|1,u<<1|1);
Node(u<<1 , tmp<<1|1) , Node(u<<1 , cnt_p<<1);
}
else Node(u<<1 , cnt_p<<1) , Node(cnt_p<<1|1,u<<1|1);
tmp = cnt_p;
}
}
for(register int i=2;i<=(cnt_p<<1|1);i++) if(!dfn[i]) dfs(i);
for(register int i=1;i<=cnt_p;i++) if(c[i<<1] == c[i<<1|1]){ puts("NIE");return 0; }
puts("TAK");
}

最后

以上就是无奈发卡为你收集整理的魏（2-sat）（前缀建边优化）的全部内容，希望文章能够帮你解决魏（2-sat）（前缀建边优化）所遇到的程序开发问题。

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