[CF1215 F] Radio Stations (2

admin 管理员组

文章数量: 886993

[CF1215 F] Radio Stations (2

点这里看题目

题目

一道 2-Sat 思维好题。
网上的题意大多讲得不是很清楚，读题耗费了许多时间，我于是决定仔细解释一下题意：（还是看不懂就换个题意看吧，语文太差~）

大致题意：

有 p p p 种电站，需要选择一种电站序列使其满足：

• n n n 对 ( x , y ) (x,y) (x,y),， x x x 电站或 y y y 电站中至少有一个
• m m m 对 ( x , y ) (x,y) (x,y)， x x x 电站或 y y y 电站中最多有一个

如果只是这样，这不就是道2-Sat的板题吗？然而还有一个限制——

• 第 i i i 种电站有两个参数 l i li li 和 r i ri ri，表示其覆盖的区间为 [ l i , r i ] [li,ri] [li,ri]。若选定一个电站序列，序列中所有电站覆盖区间的交集不能为空。题目中要求，若求得一种合法电站序列，输出交集中任意一个点，下面记这个满足条件的 “点” 为 F F F。

讲得还算清楚吧

思路

2-Sat的精髓就在于建图，建完图就是一道LQY这种菜鸡都能A的题了。 —— JZM

秉承着JZM的思想，我们考虑如何建图：

首先， n n n 对至少和 m m m 对最多，是很常见的建图方式，略过。

那么我们的难点在于，如何在图上表示出每个电站的覆盖区间和主频 F F F 的选择。

覆盖区间

由于我也不知道是如何想到这么精妙的构图方法的，我直接讲做法吧。

我们考虑一个类似于前缀和的东西。对于一个区间 [ l , r ] [l,r] [l,r]，我们把它拆成 1 − ( l − 1 ) 1-(l-1) 1−(l−1) 和 1 − r 1-r 1−r，那么我们的一对 l , r l,r l,r 可以使用这样的三种边将其替代：

1. 若选择了 i i i 号电台，则 F F F 一定不 ∈ [ 1 − ( l − 1 ) ] \in[1-(l-1)] ∈[1−(l−1)]，若 F F F ∈ [ 1 − ( l − 1 ) ] \in[1-(l-1)] ∈[1−(l−1)]，则一定不选择 i i i 号电台，大致的建边方式为 G[Yes( i )].pushback(No(p + l[i] - 1)); G[Yes(p + l[i] - 1)].pushback(No( i )) \text{G[Yes( i )].pushback(No(p + l[i] - 1)); G[Yes(p + l[i] - 1)].pushback(No( i ))} G[Yes( i )].pushback(No(p + l[i] - 1)); G[Yes(p + l[i] - 1)].pushback(No( i ))
   其中， Yes( i ) \text{Yes( i )} Yes( i ) 表示选 i i i 号电台， Yes(p + i) \text{Yes(p + i)} Yes(p + i) 表示主频选择满足 ∈ [ 1 , i ] \in[1,i] ∈[1,i]， N o No No 反之

2. 若 F ∈ [ 1 , l i − 1 ] F\in[1,li-1] F∈[1,li−1]，则 i i i 号电台无法启用，建边方式为： G[No(p + r[i])].pushback(No( i )) \text{G[No(p + r[i])].pushback(No( i ))} G[No(p + r[i])].pushback(No( i ))

3. 若 F ∉ [ 1 , r ] F\notin[1,r] F∈/​[1,r]，则 i i i 号电台无法启用，建边方式为： G[Yes( i )].pushback(Yes(p + r[i])); \text{G[Yes( i )].pushback(Yes(p + r[i]));} G[Yes( i )].pushback(Yes(p + r[i]));

妙啊！

主频选择

这个就好想得多了：

• 若 F ∈ [ 1 , l ] F\in[1,l] F∈[1,l] 满足的，那么 [ 1 , l + 1 ] [1,l+1] [1,l+1]一定满足
• 若 F ∈ [ 1 , r ] F\in[1,r] F∈[1,r] 不满足的，那么 [ 1 , r − 1 ] [1,r-1] [1,r−1]一定满足

至此为止，建边大概就差不多了，细节的东西大家注意着写吧。例如 F ! = 0 F\ != 0 F !=0， 则—— G[Yes( p )].pushback(No( p )) \text{G[Yes( p )].pushback(No( p ))} G[Yes( p )].pushback(No( p )) 就行了对吧，这样选 F = 0 F=0 F=0就一定非法了。

代码

所以开始打代码！回到那句话：

2-Sat的精髓就在于建图，建完图就是一道LQY这种菜鸡都能A的题了。 —— JZM

然而调了一半天，我的拓扑仍然过不了，看来我连菜鸡都不如啊！
所以只好被迫换成用 T a r j a n \mathcal{Tarjan} Tarjan 的 D f n \mathcal{Dfn} Dfn 判了，不过这真的好打多了，真香。

最后交一发——TLE！原来是又被卡 l o n g l o n g \Bbb{long long} longlong了， **** \text{****} ****！换成 i n t \Bbb{int} int 就过了。 **** \text{****} **** ！

话说有没有好心人帮我调调我的拓扑

Code:

LL n, p, M, m, x[MAXN], y[MAXN], l[MAXN], r[MAXN], u[MAXN], v[MAXN];inline LL Yes(LL x)
{return x << 1;
}inline LL No(LL x)
{return x << 1 | 1;
}int main()
{read( n ); read( p ); read( M ); read( m );for (Int i = 0; i < n; ++ i){read( x[i] ); read( y[i] );x[i] --, y[i] --;G[No( x[i] )].push_back( Yes( y[i] ) );G[No( y[i] )].push_back( Yes( x[i] ) );}for (Int i = 0; i < M; ++ i){G[Yes(p + i)].push_back(Yes(p + i + 1));G[No(p + i + 1)].push_back(No(p + i));}G[Yes( p )].push_back(No( p ));for (Int i = 0; i < p; ++ i){read( l[i] ); read( r[i] );G[Yes( i )].push_back(No(p + l[i] - 1));G[Yes(p + l[i] - 1)].push_back(No( i ));G[Yes( i )].push_back(Yes(p + r[i]));G[No(p + r[i])].push_back(No( i ));}for (Int i = 0; i < m; ++ i){read( u[i] ); read( v[i] );u[i] --, v[i] --;G[Yes( u[i] )].push_back(No( v[i] ));G[Yes( v[i] )].push_back(No( u[i] ));  }for (Int i = 0; i <= No(p + M); ++ i){if (! Dfn[i])Tarjan( i );}for (Int i = 0; i <= p + M; ++ i){ if (Bel[Yes( i )] == Bel[No( i )])return ! printf("-1");Opp[Bel[Yes( i )]] = Bel[No( i )];Opp[Bel[No( i )]] = Bel[Yes( i )];}queue<LL> Q;for (Int i = 0; i <= No(p + M); ++ i){int l = G[i].size();LL x = Bel[i];for (Int j = 0; j < l; ++ j){LL to = Bel[G[i][j]];if (x == to)continue;FG[to].push_back( x );Du[x] ++; }}/* 没调过的 Topfor (Int i = 1; i <= tot; ++ i)if (! Du[i])Q.push( i );while (! Q.empty()){LL x = Q.front();Q.pop();if (! Col[x]){Col[x] = 1;Col[Opp[x]] = 2;}int l = FG[x].size();for (Int i = 0; i < l; ++ i){LL to = FG[x][i];if (-- Du[to] == 0)Q.push( to );  }}*/LL Chosen = 0;for (Int i = 0; i < p; ++ i)if (Col[Yes( i )] < Col[No( i )])Chosen ++;for (Int i = 1; i <= M; ++ i)if (Col[Yes(p + i)] < Col[No(p + i)]){printf("%d %d\n", Chosen, i);break;}for (Int i = 0; i < p; ++ i)if (Col[Yes( i )] < Col[No( i )])printf("%d ", i + 1);

本文标签： CF1215 F Radio Stations (2