傳送門

文章目錄

• 題意：
• 思路：

題意：

給你$n$個(gè)點(diǎn)$m$調(diào)變的無(wú)向圖被分成$k$個(gè)部分，每個(gè)部分包含若干點(diǎn)，請(qǐng)選擇一些關(guān)鍵點(diǎn)，使得每個(gè)部分恰好有一個(gè)關(guān)鍵點(diǎn)，且每條邊至少有一個(gè)是關(guān)鍵點(diǎn)。

$1\le k,w\le n\le 1e6$

思路：

首先每條邊至少一個(gè)是關(guān)鍵點(diǎn)，這個(gè)是$2?sat$的套路建邊了，假設(shè)這個(gè)邊是$(a,b)$，那么應(yīng)該$a^{\prime }?>b,b^{\prime }?>a$。

其次每個(gè)部分恰好一個(gè)關(guān)鍵點(diǎn)，這個(gè)看起來(lái)并不是很好建圖，因?yàn)楸┝▓D的話是$n^2$級(jí)別的邊，顯然不行。我們對(duì)于這種區(qū)間的建邊，不是線段樹優(yōu)化就是前綴和優(yōu)化，這里使用前綴和優(yōu)化。

設(shè)$pr{e}_{i,j}$代表第$i$個(gè)部分的前$j$個(gè)點(diǎn)是否存在關(guān)鍵點(diǎn)，以下簡(jiǎn)稱為$pr{e}_j$。

根據(jù)這個(gè)來(lái)限制一下每個(gè)部分，寫出如下限制：
$(1)$ $a_j?>pr{e}_j,pr{e}_j^{\prime }?>a_j^{\prime }$。

$(2)$ $pr{e}_{j?1}?>a_j^{\prime },a_j?>pr{e}_{j?1}^{\prime }$。

$(3)$ $pr{e}_{j?1}?>pr{e}_j,pr{e}_j^{\prime }?>pr{e}_{j?1}^{\prime }$。

不難發(fā)現(xiàn)這些條件已經(jīng)足夠了，直接跑個(gè)$2?sat$即可。

// Problem: F. Radio Stations // Contest: Codeforces - Codeforces Round #585 (Div. 2) // URL: https://codeforces.com/contest/1215/problem/F // Memory Limit: 256 MB // Time Limit: 7000 ms // // Powered by CP Editor (https://cpeditor.org)//#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math") //#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tune=native") //#pragma GCC optimize(2) #include<cstdio> #include<iostream> #include<string> #include<cstring> #include<map> #include<cmath> #include<cctype> #include<vector> #include<set> #include<queue> #include<algorithm> #include<sstream> #include<ctime> #include<cstdlib> #include<random> #include<assert.h> #include<cassert> #define X first #define Y second #define L (u<<1) #define R (u<<1|1) #define pb push_back #define mk make_pair #define Mid ((tr[u].l+tr[u].r)>>1) #define Len(u) (tr[u].r-tr[u].l+1) #define random(a,b) ((a)+rand()%((b)-(a)+1)) #define db puts("---") using namespace std;//void rd_cre() { freopen("d://dp//data.txt","w",stdout); srand(time(NULL)); } //void rd_ac() { freopen("d://dp//data.txt","r",stdin); freopen("d://dp//AC.txt","w",stdout); } //void rd_wa() { freopen("d://dp//data.txt","r",stdin); freopen("d://dp//WA.txt","w",stdout); }typedef long long LL; typedef unsigned long long ULL; typedef pair<int,int> PII;const int N=4001010,M=N*20,mod=1e9+7,INF=0x3f3f3f3f; const double eps=1e-6;int n,m,k; int e[M],ne[M],h[N],idx; int dfn[N],low[N],id[N],tot,cnt; int stk[N],top; bool in[N];void add(int a,int b) {e[idx]=b,ne[idx]=h[a],h[a]=idx++; }void tarjan(int u) {dfn[u]=low[u]=++tot;stk[++top]=u; in[u]=true;for(int i=h[u];~i;i=ne[i]){int ver=e[i];if(!dfn[ver]){tarjan(ver);low[u]=min(low[u],low[ver]);}else if(in[ver]) low[u]=min(low[u],dfn[ver]);}if(dfn[u]==low[u]){int y; ++cnt;do{y=stk[top--];in[y]=false; id[y]=cnt;}while(y!=u);} }int yes(int x) { return x<<1; }int no(int x) { return x<<1|1; }void link(int x,int y) {add(x,y); add(y^1,x^1); }bool check() {for(int i=0;i<=n+n;i++) if(id[yes(i)]==id[no(i)]) return false;return true; }int main() { // ios::sync_with_stdio(false); // cin.tie(0);scanf("%d%d%d",&n,&m,&k);idx=0;memset(h,-1,sizeof(h));for(int i=1;i<=m;i++) {int a,b; scanf("%d%d",&a,&b);a--; b--;link(no(a),yes(b));}for(int i=1,st=n;i<=k;i++) {int cnt; scanf("%d",&cnt);for(int j=st;j<=st+cnt-1;j++) {int x; scanf("%d",&x); x--;link(yes(x),yes(j)); if(j!=st) link(yes(j-1),no(x)); if(j!=st+cnt-1) link(yes(j),yes(j+1)); }st+=cnt;}for(int i=0;i<=no(n+n);i++) if(!dfn[i]) tarjan(i);if(check()) {puts("TAK");} else puts("NIE");return 0; }

總結(jié)

以上是生活随笔為你收集整理的P6378 [PA2010] Riddle 2-sat + 前缀和优化建图的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。