2-SAT专题(2)
6. POJ 2296 Map Labeler
题意：
平面区域内部有n个点，以这个点为上底边中心或者下底边中心作正方形，要求使所有正方形都不相交，问正方形最大的边长为多少。
思路：
和炸弹那道题差不多，二分区间，判断即可。
令( Dis_x [a][b] = \left| x[a] – x[b] \right| , Dis_y [a][b] = \left| y[a] – y[b] \right| )，边长为 mid，设 a 表示 a 矩阵放上面，~a 表示 a 矩阵放下面。
建图：
- (Dis_x[a][b] \geq mid ) 或者 ( Dis_y[a][b] \geq 2 \times mid ) 不处理
- 否则 ( Dis_y[a][b] \geq mid ) 加边 ~a -> ~b , b -> a 。
- 否则 (Dis_y[a][b] > 0 ) 加边 ~a -> a , b -> ~b 。 （其实就是表示，如果你选了 ~a , b 就会适应失败。
- 否则 即 (Dis_y[a][b] = 0 ) 加边 a -> ~b , ~a -> b ,b -> ~a ,~b -> a 。
这里扯一句其他的，如果要求适应点为 n 数组一定要开 2n 呀！！！！
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int maxn = 205;
int idx, n, scc, top, vis_time;
int head[maxn], dfn[maxn], low[maxn], color[maxn], st[maxn];
bool instack[maxn];
int dis_x[maxn][maxn], dis_y[maxn][maxn];
struct point {
int x, y;
bool operator<(const point& a) const
{
return y > a.y;
}
} points[maxn];
struct node {
int to;
int nxt;
} edges[40005];
void addEdge(int u, int v)
{
edges[idx].to = v;
edges[idx].nxt = head[u];
head[u] = idx++;
}
void init()
{
for (int i = 0; i <= 2 * n; i++) {
head[i] = -1;
dfn[i] = -1;
instack[i] = false;
}
vis_time = top = idx = scc = 0;
}
void tarjan(int u)
{
int v;
low[u] = dfn[u] = vis_time++;
instack[u] = true;
st[++top] = u;
for (int id = head[u]; ~id; id = edges[id].nxt) {
v = edges[id].to;
if (dfn[v] == -1) {
tarjan(v);
low[u] = min(low[u], low[v]);
} else if (instack[v])
low[u] = min(low[u], dfn[v]);
}
if (dfn[u] == low[u]) {
scc++;
do {
v = st[top--];
instack[v] = false;
color[v] = scc;
} while (v != u);
}
}
bool judge(int side)
{
init();
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++)
if (dis_x[i][j] < side && dis_y[i][j] < 2 * side) {
if (dis_y[i][j] >= side) {
addEdge(i << 1 | 1, j << 1 | 1);
addEdge(j << 1, i << 1);
} else if (dis_y[i][j] > 0) {
addEdge(i << 1 | 1, i << 1);
addEdge(j << 1, j << 1 | 1);
} else {
addEdge(i << 1, j << 1 | 1);
addEdge(i << 1 | 1, j << 1);
addEdge(j << 1, i << 1 | 1);
addEdge(j << 1 | 1, i << 1);
}
}
for (int i = 0; i < (n << 1); i++)
if (dfn[i] == -1)
tarjan(i);
bool flag = true;
for (int i = 0; i < n; i++)
if (color[i << 1] == color[i << 1 | 1]) {
flag = false;
break;
}
return flag;
}
int main()
{
int T;
scanf("%d", &T);
while (T--) {
scanf("%d", &n);
for (int i = 0; i < n; i++)
scanf("%d %d", &points[i].x, &points[i].y);
sort(points, points + n);
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++) {
dis_x[i][j] = abs(points[i].x - points[j].x);
dis_y[i][j] = abs(points[i].y - points[j].y);
}
int le = 0, ri = 14500, mid;
while (le <= ri) {
mid = (le + ri) >> 1;
if (judge(mid))
le = mid + 1;
else
ri = mid - 1;
}
printf("%d\n", le - 1);
}
return 0;
}
7. HDU 3715 Go Deeper
题意：
给你一个递归函数，其参数分别为 深度dep 和三个其他的a,b,c。其中a,b都是另一个数组的ary的下标，如果ary[a]+ary[b]!=c 则可以向下递归。
思路：
因为所给的数据中，ary数组较小，最大深度较大，所以我们对深度进行二分。对每一个mid重新插入数据并跑一次2-sat即可。
写这道题的时候因为我的二分只是欠缺，导致一直A不了，补了一下二分后还好说。我的二分进阶
还请注意数组大小，开小了居然 G++是TLE ，C++是 WA
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int maxn = 405;
int idx, n, m, scc, top, vis_time;
int head[maxn], dfn[maxn], low[maxn], color[maxn], st[maxn];
bool instack[maxn];
int a[10005], b[10005], c[10005];
struct node {
int to;
int nxt;
} edges[40005];
void addEdge(int u, int v)
{
edges[idx].to = v;
edges[idx].nxt = head[u];
head[u] = idx++;
}
void init(int k)
{
for (int i = 0; i <= 2 * k; i++) {
head[i] = -1;
dfn[i] = -1;
instack[i] = false;
}
vis_time = top = idx = scc = 0;
}
void tarjan(int u)
{
int v;
low[u] = dfn[u] = vis_time++;
instack[u] = true;
st[++top] = u;
for (int id = head[u]; ~id; id = edges[id].nxt) {
v = edges[id].to;
if (dfn[v] == -1) {
tarjan(v);
low[u] = min(low[u], low[v]);
} else if (instack[v])
low[u] = min(low[u], dfn[v]);
}
if (dfn[u] == low[u]) {
scc++;
do {
v = st[top--];
instack[v] = false;
color[v] = scc;
} while (v != u);
}
}
inline void insertEdge(const int& a, const int& b, const int& c)
{
if (c == 0) {
addEdge(a << 1, b << 1 | 1);
addEdge(b << 1, a << 1 | 1);
} else if (c == 1) {
addEdge(a << 1, b << 1);
addEdge(b << 1, a << 1);
addEdge(a << 1 | 1, b << 1 | 1);
addEdge(b << 1 | 1, a << 1 | 1);
} else {
addEdge(a << 1 | 1, b << 1);
addEdge(b << 1 | 1, a << 1);
}
}
int main()
{
int T;
scanf("%d", &T);
while (T--) {
scanf("%d %d", &n, &m);
for (int i = 1; i <= m; i++)
scanf("%d %d %d", a + i, b + i, c + i);
int l = 0, r = m, mid;
while (l <= r) {
mid = (l + r) >> 1;
init(n);
for (int i = 1; i <= mid; i++)
insertEdge(a[i], b[i], c[i]);
bool flag = true;
for (int i = 0; i < 2 * n; i++)
if (dfn[i] == -1)
tarjan(i);
for (int i = 0; i < n; i++)
if (color[i << 1] == color[i << 1 | 1]) {
flag = false;
break;
}
if (flag)
l = mid + 1;
else
r = mid - 1;
}
printf("%d\n", l - 1);
}
return 0;
}
8. POJ 2749 Building roads
题意：
题目非常长……并且很繁琐，大意就是 n 个点要通过 一块中转站 进行相互连接。 中转站有两个提供选择，有些兄弟节点必须选择同一个中转站，有些仇人节点必须选择不同的中转站，每个节点和中转站的位置固定，要你使得任意节点之间的距离中的最大值最小。
思路：
傻了吧。
首先这种最值问题联系到二分肯定是没错了的。我们要求的这个距离 len 是在所有节点中是最大的，那么如果有两个节点的距离比我们的 len 要大，那么就产生了一个冲突。
因此我们只要二分这个 len 就可以了。
a 表示 a 节点选择 0 中转站 ，~a 表示 a 节点选择 1 中转站
dis[x][0] 表示 x 到 0 号中转站的距离，dis[x][1] 表示 x 到 1 号中转站的距离
d 表示 两个中转站的距离
建图：
| 情况 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| 兄弟节点 | a -> b | ~a -> ~b | b -> a | ~b -> ~a |
| 仇人节点 | a -> ~b | ~a -> b | b -> ~a | ~b -> a |
| dis[a][0]+dis[b][0] > len | a -> ~b | b -> ~a | ||
| dis[a][1]+dis[b][1] > len | ~a -> b | ~b -> a | ||
| dis[a][0]+dis[b][1] + d > len | a -> b | ~b -> ~a | ||
| dis[a][1]+dis[b][0] + d > len | a -> ~b | b -> a |
通过备份 head 数组和 idx 可以还原回到任意位置。
就比如说我们这道题，兄弟节点与仇人节点最多会达到 8000 个操作，而我还原 heed 数组只要 1000 个操作，并省下一部分内存。至于这个性质为什么成立，熟悉邻接表的yy一下就可以得出来这是显然的。这里就不证明了。
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int maxn = 2005;
int idx, n, scc, top, vis_time, a, b;
int head[maxn], dfn[maxn], low[maxn], color[maxn], st[maxn];
bool instack[maxn];
int tmp_head[maxn], tmp_idx;
int dis[maxn][2], s_dis;
int tx[maxn], ty[maxn];
struct node {
int to;
int nxt;
} edges[800005];
void addEdge(int u, int v)
{
edges[idx].to = v;
edges[idx].nxt = head[u];
head[u] = idx++;
}
void init()
{
for (int i = 0; i <= 2 * n; i++) {
head[i] = -1;
dfn[i] = -1;
instack[i] = false;
}
vis_time = top = idx = scc = 0;
}
void tarjan(int u)
{
int v;
low[u] = dfn[u] = vis_time++;
instack[u] = true;
st[++top] = u;
for (int id = head[u]; ~id; id = edges[id].nxt) {
v = edges[id].to;
if (dfn[v] == -1) {
tarjan(v);
low[u] = min(low[u], low[v]);
} else if (instack[v])
low[u] = min(low[u], dfn[v]);
}
if (dfn[u] == low[u]) {
scc++;
do {
v = st[top--];
instack[v] = false;
color[v] = scc;
} while (v != u);
}
}
bool judge(int mid)
{
for (int i = 0; i <= 2 * n; i++) {
dfn[i] = -1;
instack[i] = false;
}
vis_time = top = scc = 0;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (dis[i][0] + dis[j][0] > mid) {
addEdge(i << 1, j << 1 | 1);
addEdge(j << 1, i << 1 | 1);
}
if (dis[i][1] + dis[j][1] > mid) {
addEdge(i << 1 | 1, j << 1);
addEdge(j << 1 | 1, i << 1);
}
if (dis[i][0] + dis[j][1] + s_dis > mid) {
addEdge(i << 1, j << 1);
addEdge(j << 1 | 1, i << 1 | 1);
}
if (dis[i][1] + dis[j][0] + s_dis > mid) {
addEdge(i << 1 | 1, j << 1 | 1);
addEdge(j << 1, i << 1);
}
}
}
for (int i = 0; i < (n << 1); i++)
if (dfn[i] == -1)
tarjan(i);
for (int i = 0; i < n; i++)
if (color[i << 1] == color[i << 1 | 1])
return false;
return true;
}
int main()
{
int a, b, na, nb;
int sx[2], sy[2];
while (scanf("%d %d %d", &n, &a, &b) != EOF) {
init();
scanf("%d %d %d %d", &sx[0], &sy[0], &sx[1], &sy[1]);
s_dis = abs(sx[0] - sx[1]) + abs(sy[0] - sy[1]);
for (int i = 0; i < n; i++) {
scanf("%d %d", &na, &nb);
dis[i][0] = abs(na - sx[0]) + abs(nb - sy[0]);
dis[i][1] = abs(na - sx[1]) + abs(nb - sy[1]);
}
for (int i = 0; i < a; i++) {
scanf("%d %d", &na, &nb);
na--, nb--;
addEdge(na << 1, nb << 1 | 1);
addEdge(na << 1 | 1, nb << 1);
addEdge(nb << 1, na << 1 | 1);
addEdge(nb << 1 | 1, na << 1);
}
for (int i = 0; i < b; i++) {
scanf("%d %d", &na, &nb);
na--, nb--;
addEdge(na << 1, nb << 1);
addEdge(na << 1 | 1, nb << 1 | 1);
addEdge(nb << 1, na << 1);
addEdge(nb << 1 | 1, na << 1 | 1);
}
memcpy(tmp_head, head, sizeof head);
tmp_idx = idx;
int le = 0, ri = 4000000, mid;
while (le <= ri) {
mid = (le + ri) >> 1;
if (judge(mid))
ri = mid - 1;
else
le = mid + 1;
memcpy(head, tmp_head, sizeof tmp_head);
idx = tmp_idx;
}
printf("%d\n", ri == 4000000 ? -1 : ri + 1);
}
return 0;
}
9. POJ 2723 Get Luffy Out
好题！
题意：
有个地牢有 m 层，所谓地牢，当然只有你通过了 d 层才能进入 d+1 层。每一层都有一扇大门，只有打开它才能进入下一层，每一扇大门有两把锁，只要你打开一种一扇就能打开这扇大门。而我们有 n 串钥匙，一串2把 ，一旦使用了其中一把，另一把就会消失。问最深能进入多少层。
思路：
数据不是很大，不二分也都可以过。
对于一道 2-SAT 题，我们最主要的是要抓住它的矛盾所在。对于一扇门，两把锁，如果我们要打开它，就必须有一把钥匙存在。换言之，打开这扇门 与 这扇门上的两把钥匙都不存在 矛盾！
假设锁 X,Y 对应 钥匙 x,y , 建边 ~x -> y ，~y -> x
这里不得不感慨 2-SAT 的逻辑性之强，我自己实在是一时间没有想到，就看题解去了。而这里最妙的地方并不是在这里。这道题是我第一道（微小地）跳出模板的题。
上面刚说了， 2-SAT 的重点就是抓住它的矛盾所在，以往的题，两个矛盾相对都是自己决定的，而这题却是题目给定的。详细的看 judge 函数。
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int maxn = 10005;
int idx, n, m, scc, top, vis_time;
int head[maxn], dfn[maxn], low[maxn], color[maxn], st[maxn];
bool instack[maxn];
int refer[maxn], a[maxn], b[maxn];
int key[maxn][2];
struct node {
int to;
int nxt;
} edges[800005];
void addEdge(int u, int v)
{
edges[idx].to = v;
edges[idx].nxt = head[u];
head[u] = idx++;
}
void init()
{
for (int i = 0; i <= 2 * n; i++) {
head[i] = -1;
dfn[i] = -1;
instack[i] = false;
}
vis_time = top = idx = scc = 0;
}
void tarjan(int u)
{
int v;
low[u] = dfn[u] = vis_time++;
instack[u] = true;
st[++top] = u;
for (int id = head[u]; ~id; id = edges[id].nxt) {
v = edges[id].to;
if (dfn[v] == -1) {
tarjan(v);
low[u] = min(low[u], low[v]);
} else if (instack[v])
low[u] = min(low[u], dfn[v]);
}
if (dfn[u] == low[u]) {
scc++;
do {
v = st[top--];
instack[v] = false;
color[v] = scc;
} while (v != u);
}
}
bool judge(int mid)
{
int u, v;
init();
for (int i = 0; i < mid; i++) {
u = a[i], v = b[i];
addEdge(refer[u], v);
addEdge(refer[v], u);
}
for (int i = 0; i < (n << 1); i++)
if (dfn[i] == -1)
tarjan(i);
for (int i = 0; i < n; i++)
if (color[i] == color[refer[i]]) //看这里！！
return false;
return true;
}
int main()
{
int u, v;
while (scanf("%d %d", &n, &m) != EOF) {
if (n == 0 && m == 0)
break;
for (int i = 0; i < n; i++) {
scanf("%d %d", &u, &v);
refer[u] = v;
refer[v] = u;
}
for (int i = 0; i < m; i++)
scanf("%d %d", a + i, b + i);
int le = 0, ri = m, mid;
while (le <= ri) {
mid = (le + ri) >> 1;
if (judge(mid))
le = mid + 1;
else
ri = mid - 1;
}
printf("%d\n", le - 1);
}
return 0;
}