Codeforces

Luogu

分析

很神仙的 2-SAT 。

设表示第 $i$ 个电台启用的点为 $yes(i)$ ,表示第 $i$ 个电台不启用的点为 $no_i$ 。

先考虑一下 $u$ 和 $v$ 至少启用一个怎么连边。连 $no(u)\to yes(v)$ 和 $no(v)\to yes(u)$ 即可。

再考虑一下 $u$ 和 $v$ 不能同时启用怎么连边。连 $yes(u)\to no(v)$ 和 $yes(v)\to no(u)$ 即可。

现在我们主要考虑,怎么表示当 $f\notin[l_i,r_i]$ 时第 $i$ 个电台不能启用。

令 $yes(id_i)$ 为表示 $f\leq i$ 满足的点,$no(id_i)$ 为表示 $f\leq i$ 不满足(即 $f>i$ 满足)的点。

首先就可以连出一些边:$yes(id_i)\to yes(id_{i+1})$ 和 $no(id_{i+1})\to no(id_i)$ 。

然后考虑 $f$ 对电台的限制。连如下边:

  • $yes(i)\to no(id_{l_i-1})$ 和 $yes(id_{l_i-1})\to no(i)$ 。
  • $yes(i)\to yes(id_{r_i})$ 和 $no(id_{r_i})\to no(i)$ 。

最后注意到我们是建了 $id_0$ 的,但是 $f$ 并不能等于 $0$ ,所以再连一条 $yes(id_0)\to no(id_0)$ 即可。

现在就很好判断无解了。至于输出方案的话,利用缩点的拓扑序判断一下即可。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=1600000+10,M=4000000+10;

int n,m,m1,m2;

inline int yes(int i) { return i<<1; }
inline int no(int i) { return i<<1|1; }
inline int id(int i) { return n+1+i; }

struct edge { int v,nxt; } e[M];
int head[N];
inline void addEdge(int u,int v) {
    static int cnt=0;
    e[++cnt]=(edge){v,head[u]},head[u]=cnt;
}

int dfn[N],low[N],tim=0,bl[N],tot=0,sta[N],in[N],top=0;
inline void tarjan(int u) {
    dfn[u]=low[u]=++tim,sta[++top]=u,in[u]=1;
    for (re int i=head[u];i;i=e[i].nxt) {
        int v=e[i].v;
        if (!dfn[v]) tarjan(v),low[u]=min(low[u],low[v]);
        else if (in[v]) low[u]=min(low[u],dfn[v]);
    }
    if (dfn[u]==low[u]) { ++tot;
        while (233) {
            int t=sta[top--]; bl[t]=tot,in[t]=0;
            if (t==u) break;
        }
    }
}

int main() {
    m1=read(),n=read(),m=read(),m2=read();
    for (re int i=1;i<=m1;++i) { int u=read(),v=read();
        addEdge(no(u),yes(v)),addEdge(no(v),yes(u));
    }
    for (re int i=1;i<=n;++i) { int l=read(),r=read();
        addEdge(yes(i),no(id(l-1))),addEdge(yes(id(l-1)),no(i));
        addEdge(yes(i),yes(id(r))),addEdge(no(id(r)),no(i));
    }
    for (re int i=1;i<=m2;++i) { int u=read(),v=read();
        addEdge(yes(u),no(v)),addEdge(yes(v),no(u));
    }
    for (re int i=0;i<m;++i)
        addEdge(yes(id(i)),yes(id(i+1))),addEdge(no(id(i+1)),no(id(i)));
    addEdge(yes(id(0)),no(id(0)));
    
    for (re int i=1;i<=no(id(m));++i) if (!dfn[i]) tarjan(i);
    for (re int i=1;i<=n+m+1;++i)
        if (bl[yes(i)]==bl[no(i)]) { puts("-1"); return 0; }
    int k=0;
    for (re int i=1;i<=n;++i)
        if (bl[yes(i)]<bl[no(i)]) ++k;
    for (re int f=1;f<=m;++f)
        if (bl[yes(id(f))]<bl[no(id(f))]) { printf("%d %d\n",k,f); break; }
    for (re int i=1;i<=n;++i)
        if (bl[yes(i)]<bl[no(i)]) printf("%d ",i);
    puts("");
    return 0;
}
最后修改:2019 年 09 月 29 日 11 : 46 AM