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

96 阅读 0 评论 64 点赞

我是靠谱客的博主无奈发卡，这篇文章主要介绍魏（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不裸。。。。。。里面前缀优化的时候似乎是全程 $x o r$ 所以才可以 $2 - s a t$ 的。

复制代码

#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");
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
#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");
}