CF1215F Radio Stations

@Pelom  September 26, 2019

题意

有$n$个要求,要求电台$x_i$与$y_i$中至少选择$1$个
共$p$个电台,满足一个电台的信号功率范围为$[l_i,r_i]$
在$[1,M]$选择一个信号功率,要求满足选择的所有电台
有$m$对电台不能同时选择
判断是否能够满足,如果是,输出方案

数据范围:$2 \le n,p,M,m \le 4 \cdot 10^5$

题解

对于至少选择一个和不能同时选择的要求,我们容易看出这是一个$2-SAT$问题
用节点$x_i$表示选择电台$x_i$,用节点$x_i+p$表示不选择$x_i$
则要求从$x_i$与$y_i$中至少选择$1$个可以拆解为不选择$y_i \rightarrow$选择$x_i$不选择$x_i \rightarrow$选择$y_i$
建边$$y_i+p \rightarrow x_i$$$$x_i+p \rightarrow y_i$$
相似的,不能同时选择可以拆解为选择$x_i \rightarrow$不选择$y_i$选择$y_i \rightarrow$不选择$x_i$
建边$$x_i \rightarrow y_i+p$$$$y_i \rightarrow x_i+p$$
现在还需要解决信号功率的限制,选择一个电台后我们无法得知一个确定的信号功率来约束它,但我们知道哪些信号功率不能选,因此由$i$向$[1,l_i-1] \cup [r_i+1,M]$对应的节点建边,并且由$[l_i,r_i]$对应的节点向$i+p$建边,意为不选择此段范围中的信号功率便不能选择$i$
但是如果这样建边的话空间时间都承受不了,考虑将建边的对象转化为区间,能不能向区间的两端建边表示对这段区间的选择与否呢?这样是可以的,由$i$向信号频率为$x$对应的节点建边,表示不能选择小于$x$的信号频率,可是如果我们要表示不能选择大于$x$的信号频率呢?再额外使用$M$个节点保存大于的信息就好了
而要保存区间连续的关系,还需在区间中向相邻的值建边,如下

tot=p<<1;
pre[1]=++tot;
suc[1]=tot+M;
for(int i=2;i<=M;i++){
    pre[i]=++tot;
    suc[i]=tot+M;
    add(pre[i],pre[i-1]);
    add(suc[i-1],suc[i]);
}

至此,约束条件已经被全部写入图中,跑一次$Tarjan$即可得知是否存在方案,而输出答案,只需取满足条件的$max(l_i)$作为最后选定的信号功率(因为题目未作额外要求)

代码:

#include<iostream>
#include<cstdio>
#include<stack>
using namespace std;
const int N=4e5+10;
stack<int> S;
int n,p,M,m,x,y;
int l[N],r[N];
int cnt,tot,dep,cc,ans;
int head[N<<2],pre[N],suc[N],dfn[N<<2],low[N<<2],clr[N<<2],a[N];
struct edge{
    int nxt,to;
} e[N*10];
template <typename T>
inline T Max(T a,T b){
    return a>b?a:b;
}
template <typename T>
inline T Min(T a,T b){
    return a<b?a:b;
}
inline void add(int u,int v){
    e[++cnt]=(edge){head[u],v};
    head[u]=cnt;
}
void Tarjan(int u){
    dfn[u]=low[u]=++dep;
    S.push(u);
    for(int i=head[u];i;i=e[i].nxt){
        int v=e[i].to;
        if(!dfn[v]){
            Tarjan(v);
            low[u]=Min(low[u],low[v]);
        }
        else if(!clr[v])
            low[u]=Min(low[u],dfn[v]);
    }
    if(dfn[u]==low[u]){
        cc++;
        for(int t;t!=u;){
            t=S.top();
            S.pop();
            clr[t]=cc;
        }
    }
}
int main(){
    scanf("%d%d%d%d",&n,&p,&M,&m);
    tot=p<<1;
    pre[1]=++tot;
    suc[1]=tot+M;
    for(int i=2;i<=M;i++){
        pre[i]=++tot;
        suc[i]=tot+M;
        add(pre[i],pre[i-1]);
        add(suc[i-1],suc[i]);
    }
    for(int i=1;i<=n;i++){
        scanf("%d%d",&x,&y);
        add(x+p,y);
        add(y+p,x);
    }
    for(int i=1;i<=p;i++){
        scanf("%d%d",&l[i],&r[i]);
        if(l[i]-1>=1)
            add(i,pre[l[i]-1]);
        if(r[i]+1<=M)
            add(i,suc[r[i]+1]);
        add(suc[l[i]],i+p);
        add(pre[r[i]],i+p);
    }
    for(int i=1;i<=m;i++){
        scanf("%d%d",&x,&y);
        add(x,y+p);
        add(y,x+p);
    }
    for(int i=1;i<=(p<<1);i++)
        if(!dfn[i])
            Tarjan(i);
    for(int i=1;i<=p;i++)
        if(clr[i]==clr[i+p]){
            puts("-1");
            return 0;
        }
    for(int i=1;i<=p;i++)
        if(clr[i]<clr[i+p]){
            ans=Max(ans,l[i]);
            a[++*a]=i;
        }
    printf("%d %d\n",*a,ans);
    for(int i=1;i<=*a;i++)
        printf("%d ",a[i]);
    return 0;
}

添加新评论