我是靠谱客的博主 高大煎蛋,这篇文章主要介绍BZOJ 3495: PA2010 Riddle 2-SAT:前缀优化建图titleanalysiscode,现在分享给大家,希望可以做个参考。

title

BZOJ 3495
Description

有n个城镇被分成了k个郡,有m条连接城镇的无向边。
要求给每个郡选择一个城镇作为首都,满足每条边至少有一个端点是首都。

Input

第一行有三个整数,城镇数n((1le nle10^6)),边数m((0le mle10^6)),郡数k(1<=k<=n)。
接下来m行,每行有两个整数ai和bi(ai≠bi),表示有一条无向边连接城镇ai和bi。
接下来k行,第j行以一个整数wj开头,后面是wj个整数,表示第j个郡包含的城镇。

Output

若有解输出TAK,否则输出NIE。

Sample Input

6 5 2
1 2
3 1
1 4
5 2
6 2
3 3 4 2
3 1 6 5

Sample Output

TAK

Source

鸣谢onion_cyc提供翻译

analysis

(2-SAT) 很容易看出来,关键在于怎么保证每个国家只能有一个首都。

也就是如果某一个选了,就会有后面的不能选,前面的也不能选的关系,但是边数是 (n^2) 的,难以接受。

所以就需要一个小技巧了:前缀优化建图。

细节方面见参考资料:Rising_shit 。

其实我是觉得 HYJ_cnyali 的方法更好,也很容易理解。

code

复制代码
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
#include<bits/stdc++.h> using namespace std; const int maxn=3e6+10; char buf[1<<15],*fs,*ft; inline char getc() { return (ft==fs&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),ft==fs))?0:*fs++; } template<typename T>inline void read(T &x) { x=0; T f=1, ch=getchar(); while (!isdigit(ch) && ch^'-') ch=getchar(); if (ch=='-') f=-1, ch=getchar(); while (isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48), ch=getchar(); x*=f; } template<typename T>inline void write(T x) { if (!x) { putchar('0'); return ; } if (x<0) putchar('-'), x=-x; T num=0, ch[20]; while (x) ch[++num]=x%10+48, x/=10; while (num) putchar(ch[num--]); } int ver[maxn*6],Next[maxn*6],head[maxn<<1],len=1; inline void add(int x,int y) { ver[++len]=y,Next[len]=head[x],head[x]=len; } int dfn[maxn<<1],low[maxn<<1],id; int Stack[maxn<<1],top; int belong[maxn<<1],tot; bool instack[maxn<<1]; inline void tarjan(int x) { dfn[x]=low[x]=++id; Stack[++top]=x; instack[x]=1; for (int i=head[x]; i; i=Next[i]) { int y=ver[i]; if (!dfn[y]) { tarjan(y); low[x]=min(low[x],low[y]); } else if (instack[y]) low[x]=min(low[x],dfn[y]); } if (low[x]==dfn[x]) { int k; ++tot; do { k=Stack[top--]; belong[k]=tot; instack[k]=0; } while (k!=x); } } int pre[maxn]; int main() { memset(pre,-1,sizeof(pre)); int n,m,k;read(n);read(m);read(k); for (int i=1,x,y; i<=m; ++i) read(x),read(y),--x,--y,add(y<<2|1,x<<2),add(x<<2|1,y<<2); for (int i=1,w,last; i<=k; ++i) { read(w);read(last);--last; for (int j=1,y; j<w; ++j) read(y),--y,pre[y]=last,last=y; } for (int i=0; i<n; ++i)//前缀优化建图 { int x1=i<<2,x2=x1|1,x3=x2+1,x4=x3+1; add(x1,x3),add(x4,x2); if (pre[i]!=-1) { int j=pre[i],y1=j<<2,y2=y1|1,y3=y2+1,y4=y3+1; add(y3,x3),add(x4,y4),add(y3,x2),add(x1,y4); } } for (int i=0; i<(n<<1); ++i) if (!dfn[i]) tarjan(i); for (int i=0; i<(n<<1); ++i) if (belong[i]==belong[i^1]) return puts("NIE"),0; puts("TAK"); return 0; }

转载于:https://www.cnblogs.com/G-hsm/p/11323302.html

最后

以上就是高大煎蛋最近收集整理的关于BZOJ 3495: PA2010 Riddle 2-SAT:前缀优化建图titleanalysiscode的全部内容,更多相关BZOJ内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
点赞(48)

评论列表共有 0 条评论

立即
投稿
返回
顶部