题意 2 ? S A T 2-SAT 2?SAT多了一个边的范围，其实只需要把点的范围加上去就行了即：
第 i i i个点 ( l [ i ] , r [ i ] ) (l[i], r[i]) (l[i],r[i])，那么构造点 j j j， k k k对应 l [ i ] l[i] l[i]， r [ i ] + 1 r[i]+1 r[i]+1。
j < < 1 j<<1 j<<1， j < < 1 ∣ 1 j<<1|1 j<<1∣1分别对应 v a l > = l [ i ] val >= l[i] val>=l[i]与 v a l < l [ i ] val < l[i] valk < < 1 k<<1 k<<1， k < < 1 ∣ 1 k<<1|1 k<<1∣1分别对应 v a l > = r [ i ] + 1 val >= r[i]+1 val>=r[i]+1与 v a l < r [ i ] + 1 val < r[i]+1 val 这样连接点 i < < 1 → j < < 1 i<<1 \to j<<1 i<<1→j<<1， i < < 1 → k < < 1 ∣ 1 i<<1 \to k<<1|1 i<<1→k<<1∣1，以及 j < < 1 ∣ 1 → i < < 1 ∣ 1 j<<1|1 \to i<<1|1 j<<1∣1→i<<1∣1， k < < 1 → i < < 1 ∣ 1 k<<1 \to i<<1|1 k<<1→i<<1∣1。
然后把 0 ∽ M + 1 0 \backsim M+1 0∽M+1 的点按逻辑连接起来就行了。
小trick 【Codeforces Round #585 (Div. 2) F. Radio Stations】 2 ? S A T 2-SAT 2?SAT中一条关系表达式一定能退出两条有向边，不能漏边了！！！
#include using namespace std;
vector> e;
vector l, r;
vector vis;
stack stk;
vector dfn, low, be;
int tot = 0, cnt = 0;
void tarjan(int u)
{
dfn[u] = low[u] = ++tot;
stk.push(u);
vis[u] = true;
for (auto &v : e[u]) {
if (!dfn[v]) {
tarjan(v);
low[u] = min(low[u], low[v]);
} else if (vis[v]) {
low[u] = min(low[u], dfn[v]);
}
}
if (dfn[u] == low[u]) {
++cnt;
// cout << "stk: ";
while (stk.top() != u) {
int v = stk.top();
stk.pop();
// cout << v << " ";
be[v] = cnt;
vis[v] = false;
}
// cout << u << endl;
stk.pop();
be[u] = cnt;
vis[u] = false;
}
}int main()
{
int n, p, M, m;
cin >> n >> p >> M >> m;
const int maxn = (p + M + 1) * 2 + 10;
e.assign(maxn, vector());
l.assign(p, 0);
r.assign(p, 0);
int x, y;
for (int i = 0;
i < n;
++i) {
cin >> x >> y;
--x;
--y;
e[x<<1|1].emplace_back(y<<1);
e[y<<1|1].emplace_back(x<<1);
}
for (int i = 0;
i < p;
++i) {
cin >> l[i] >> r[i];
e[i<<1].emplace_back((l[i] + p)<<1);
e[i<<1].emplace_back((r[i] + p + 1)<<1|1);
e[(l[i] + p)<<1|1].emplace_back(i<<1|1);
e[(r[i] + p + 1)<<1].emplace_back(i<<1|1);
}
for (int i = 0;
i < m;
++i) {
cin >> x >> y;
--x;
--y;
e[x<<1].emplace_back(y<<1|1);
e[y<<1].emplace_back(x<<1|1);
}
for (int i = 0;
i <= M;
++i) {
e[(i + p + 1)<<1].emplace_back((i + p)<<1);
e[(i + p)<<1|1].emplace_back((i + p + 1)<<1|1);
}
vis.assign(maxn, false);
dfn.assign(maxn, 0);
low.assign(maxn, 0);
be.assign(maxn, 0);
for (int i = 0, _i = 2 * (p + M + 1);
i <= _i;
++i)
if (!dfn[i])
tarjan(i);
for (int i = 0, _i = p + M + 1;
i <= _i;
++i) {
if (be[i<<1] == be[i<<1|1]) {
cout << -1 << endl;
return 0;
}
}
vector ans;
int val = 0;
for (int i = 0;
i < p;
++i) {
// cout << "i: " << be[i<<1] << " " << be[i<<1|1] << endl;
if (be[i<<1] < be[i<<1|1]) {
ans.emplace_back(i);
val = max(val, l[i]);
}
}
cout << ans.size() << " " << val << "\n";
for (int i = 0, _i = ans.size();
i < _i;
++i) {
if (i)
cout << " ";
cout << ans[i] + 1;
}
cout << endl;
return 0;
}
推荐阅读
