2-SAT 题目整理

其实就是把kb菊苣整理的题目刷了一遍。

poj-3648 Wedding

细节：不让新娘看到有奸情的任意一对同时在对面一侧，则必选新郎，然后构造新郎那侧的可行解，然后将染相反颜色的人输出(要求输出新娘那侧的人)。

代码1(任意可行解)：

#include <algorithm>
#include <iostream>
#include <string.h>
#include <vector>
#include <cstdio>
#include <queue> 
using namespace std;
const int maxn = 65;
const int maxm = maxn*maxn;
struct node {int u, v, next;} edge[maxm];
int no, head[maxn];
int dfn[maxn], low[maxn], index, sta[maxn], top;
bool vis[maxn];
int bel[maxn], cnt;
vector<int> g[maxn];
queue<int> q;
int opp[maxn], deg[maxn], col[maxn];
int n, m;
void init()
{
	no = 0;
	memset(head, -1, sizeof head);
	index = 0, top = 0;
	memset(dfn, 0, sizeof dfn);
	memset(vis, 0, sizeof vis);
	cnt = 0;
	memset(deg, 0, sizeof deg);
	memset(col, 0, sizeof col);
}
inline void add(int u, int v)
{
	edge[no].u = u; edge[no].v = v;
	edge[no].next = head[u]; head[u] = no++;
}
void tarjan(int u)
{
	dfn[u] = low[u] = ++index;
	sta[++top] = u, vis[u] = 1;
	for(int k = head[u]; k+1; k = edge[k].next)
	{
		int v = edge[k].v;
		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;
		do
		{
			vis[sta[top]] = 0;
			bel[sta[top]] = cnt;
			--top;
		}
		while(sta[top+1] != u);
	}
}
void print()
{
	for(int i = 1; i < n; ++i)
	{
		if(i > 1) printf(" ");
		if(col[bel[i*2]] != 1) printf("%dh", i);
		if(col[bel[i*2+1]] != 1) printf("%dw", i);
	}
	printf("\n");
}
void topsort()
{
	for(int i = 1; i <= cnt; ++i) g[i].clear();
	for(int i = 0; i < no; ++i)
	{
		int u = edge[i].u, v = edge[i].v;
		if(bel[u] == bel[v]) continue;
		g[bel[v]].push_back(bel[u]);
		++deg[bel[u]];
	}
	while(!q.empty()) q.pop();
	for(int i = 1; i <= cnt; ++i)
	if(!deg[i]) q.push(i);
	while(!q.empty())
	{
		int u = q.front(); q.pop();
		if(!col[u])
		col[u] = 1, col[opp[u]] = -1;
		for(int i = 0; i < g[u].size(); ++i)
		{
			int v = g[u][i];
			if(--deg[v] == 0) q.push(v);
		}
	}
}
void work()
{
	for(int i = 0; i < n*2; ++i)
	if(!dfn[i]) tarjan(i);
	for(int i = 0; i < n; ++i)
	{
		if(bel[i*2] == bel[i*2+1])
		{
			puts("bad luck");
			return;
		}
		else
		{
			opp[bel[i*2]] = bel[i*2+1];
			opp[bel[i*2+1]] = bel[i*2];
		} 
	}
	topsort();
	print();
}
void mapping()
{
	for(int i = 1; i <= m; ++i)
	{
		int u, v;
		char c1, c2;
		scanf("%d%c %d%c", &u, &c1, &v, &c2);
		u *= 2, v *= 2;
		if(c1 == 'w') ++u;
		if(c2 == 'w') ++v;
		add(u, (v^1));
		add(v, (u^1));
	}
	add(1, 0);
}
int main()
{
	while(~scanf("%d %d", &n, &m) && n+m)
	{
		init();
		mapping();
		work();
	}
	return 0;
}

代码2(字典序最小的解)：

#include <algorithm>
#include <iostream>
#include <string.h>
#include <vector>
#include <cstdio>
#include <queue> 
using namespace std;
const int maxn = 65;
const int maxm = maxn*maxn;
struct node {int u, v, next;} edge[maxm];
int no, head[maxn];
int col[maxn], sta[maxn], top;
int n, m;
void init()
{
	no = 0;
	memset(head, -1, sizeof head);
	memset(col, 0, sizeof col);
}
inline void add(int u, int v)
{
	edge[no].u = u; edge[no].v = v;
	edge[no].next = head[u]; head[u] = no++;
}
void print()
{
	for(int i = 1; i < n; ++i)
	{
		if(i > 1) printf(" ");
		if(col[i*2] != 1) printf("%dh", i);
		if(col[i*2+1] != 1) printf("%dw", i);
	}
	printf("\n");
}
bool dfs(int u)
{
	if(col[u^1]) return 0;
	if(col[u]) return 1;
	col[u] = 1;
	sta[++top] = u;
	for(int k = head[u]; k+1; k = edge[k].next)
	{
		int v = edge[k].v;
		if(!dfs(v)) return 0;
	}
	return 1;
}
void work()
{
	for(int i = 0; i < n; ++i)
	{
		if(col[i*2] || col[i*2+1]) continue;
		top = 0;
		if(!dfs(i*2))
		{
			while(top) col[sta[top--]] = 0;
			if(!dfs(i*2+1))
			{
				puts("bad luck");
				return;
			}
		}
	}
	print();
}
void mapping()
{
	for(int i = 1; i <= m; ++i)
	{
		int u, v;
		char c1, c2;
		scanf("%d%c %d%c", &u, &c1, &v, &c2);
		u *= 2, v *= 2;
		if(c1 == 'w') ++u;
		if(c2 == 'w') ++v;
		add(u, (v^1));
		add(v, (u^1));
	}
	add(1, 0);
}
int main()
{
	while(~scanf("%d %d", &n, &m) && n+m)
	{
		init();
		mapping();
		work();
	}
	return 0;
}

hdu-1814 Peaceful Commission

输出字典序最小的解模板题。

代码：

#include <algorithm>
#include <iostream>
#include <string.h>
#include <vector>
#include <cstdio>
#include <queue> 
using namespace std;
const int maxn = 16005;
const int maxm = 40005;
struct node {int u, v, next;} edge[maxm];
int no, head[maxn];
int col[maxn], sta[maxn], top;
int n, m;
void init()
{
    no = 0;
    memset(head, -1, sizeof head);
    memset(col, 0, sizeof col);
}
inline void add(int u, int v)
{
    edge[no].u = u; edge[no].v = v;
    edge[no].next = head[u]; head[u] = no++;
}
void print()
{
    for(int i = 0; i < n; ++i)
    {
        if(col[i*2] == 1) printf("%d\n", i*2+1);
        if(col[i*2+1] == 1) printf("%d\n", i*2+1+1);
    }
}
bool dfs(int u)
{
    if(col[u^1]) return 0;
    if(col[u]) return 1;
    col[u] = 1;
    sta[++top] = u;
    for(int k = head[u]; k+1; k = edge[k].next)
    {
        int v = edge[k].v;
        if(!dfs(v)) return 0;
    }
    return 1;
}
void work()
{
    for(int i = 0; i < n; ++i)
    {
        if(col[i*2] || col[i*2+1]) continue;
        top = 0;
        if(!dfs(i*2))
        {
            while(top) col[sta[top--]] = 0;
            if(!dfs(i*2+1))
            {
                puts("NIE");
                return;
            }
        }
    }
    print();
}
void mapping()
{
    for(int i = 1; i <= m; ++i)
    {
        int u, v;
        scanf("%d %d", &u, &v);
        --u, --v;
        add(u, (v^1));
        add(v, (u^1));
    }
}
int main()
{
    //freopen("SPO.in", "r", stdin);
    //freopen("SPO.out", "w", stdout);
    while(~scanf("%d %d", &n, &m))
    {
        init();
        mapping();
        work();
    }
    return 0;
}

poj-3678 Katu Puzzle

抽象and、or、xor的冲突建图，求可行解。

代码：

#include <algorithm>
#include <iostream>
#include <string.h>
#include <vector>
#include <cstdio>
#include <queue> 
using namespace std;
const int maxn = 1005;
const int maxm = 4e6+5;
struct node {int u, v, next;} edge[maxm];
int no, head[maxn];
int dfn[maxn], low[maxn], index, sta[maxn], top;
bool vis[maxn];
int bel[maxn], cnt;
int n, m;
void init()
{
	no = 0;
	memset(head, -1, sizeof head);
	index = 0, top = 0;
	memset(dfn, 0, sizeof dfn);
	memset(vis, 0, sizeof vis);
	cnt = 0;
}
inline void add(int u, int v)
{
	edge[no].u = u; edge[no].v = v;
	edge[no].next = head[u]; head[u] = no++;
}
void tarjan(int u)
{
	dfn[u] = low[u] = ++index;
	sta[++top] = u, vis[u] = 1;
	for(int k = head[u]; k+1; k = edge[k].next)
	{
		int v = edge[k].v;
		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;
		do
		{
			vis[sta[top]] = 0;
			bel[sta[top]] = cnt;
			--top;
		}
		while(sta[top+1] != u);
	}
}
void work()
{
	for(int i = 0; i < n*2; ++i)
	if(!dfn[i]) tarjan(i);
	for(int i = 0; i < n; ++i)
	{
		if(bel[i*2] == bel[i*2+1])
		{
			puts("NO");
			return;
		}
	}
	puts("YES");
}
void mapping()
{
	for(int i = 1; i <= m; ++i)
	{
		int u, v, w;
		char s[5];
		scanf("%d %d %d%s", &u, &v, &w, s);
		u *= 2, v *= 2;
		if(s[0] == 'A')
		{
			if(w == 1) 
			add(u+1, v+1), add(v+1, u+1), add(u, u+1), add(v, v+1);
			else 
			add(u+1, v), add(v+1, u);
		}
		if(s[0] == 'O')
		{
			if(w == 1) 
			add(u, v+1), add(v, u+1);
			else 
			add(u, v), add(v, u), add(u+1, u), add(v+1, v);
		}
		if(s[0] == 'X')
		{
			if(w == 1) 
			add(u, v+1), add(v, u+1), add(v+1, u), add(u+1, v);
			else 
			add(u, v), add(v, u), add(u+1, v+1), add(v+1, u+1);
		}
	}
}
int main()
{
	while(scanf("%d %d", &n, &m) != EOF)
	{
		init();
		mapping();
		work();
	}
	return 0;
}

hdu-3622 Bomb Game

二分构图+可行性判断。

代码：

#include <algorithm>
#include <iostream>
#include <string.h>
#include <vector>
#include <cstdio>
#include <queue> 
#include <cmath>
using namespace std;
const double eps = 1e-5;
const int maxn = 205;
const int maxm = 4*maxn*maxn;
struct node {int u, v, next;} edge[maxm];
int no, head[maxn];
int dfn[maxn], low[maxn], index, sta[maxn], top;
bool vis[maxn];
int bel[maxn], cnt;
int n;
struct coordinate {int x, y;} a[2][maxn];
double dis[4][maxn][maxn];
void init()
{
    no = 0;
    memset(head, -1, sizeof head);
    index = 0, top = 0;
    memset(dfn, 0, sizeof dfn);
    memset(vis, 0, sizeof vis);
    cnt = 0;
}
inline void add(int u, int v)
{
    edge[no].u = u; edge[no].v = v;
    edge[no].next = head[u]; head[u] = no++;
}
void tarjan(int u)
{
    dfn[u] = low[u] = ++index;
    sta[++top] = u, vis[u] = 1;
    for(int k = head[u]; k+1; k = edge[k].next)
    {
        int v = edge[k].v;
        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;
        do
        {
            vis[sta[top]] = 0;
            bel[sta[top]] = cnt;
            --top;
        }
        while(sta[top+1] != u);
    }
}
bool work()
{
    for(int i = 0; i < n*2; ++i)
    if(!dfn[i]) tarjan(i);
    for(int i = 0; i < n; ++i)
    {
        if(bel[i*2] == bel[i*2+1])
        return 0;
    }
    return 1;
}
bool mapping(double up)
{
    for(int i = 0; i < n; ++i)
    for(int j = i+1; j < n; ++j)
    {
        if(dis[0][i][j] <= up*up) add(i*2, j*2+1), add(j*2, i*2+1);
        
        if(dis[1][i][j] <= up*up) add(i*2, j*2), add(j*2+1, i*2+1);
        
        if(dis[2][i][j] <= up*up) add(i*2+1, j*2+1), add(j*2, i*2);
        
        if(dis[3][i][j] <= up*up) add(i*2+1, j*2), add(j*2+1, i*2);
    }
    return 1;
}
bool jg(double x)
{
    init();
    if(!mapping(x*2)) return 0;
    return work();
}
int main()
{
    //freopen("in.txt", "r", stdin);
    while(scanf("%d", &n) != EOF)
    {
        for(int i = 0; i < n; ++i)
        {
            scanf("%d %d", &a[0][i].x, &a[0][i].y);
            scanf("%d %d", &a[1][i].x, &a[1][i].y);
        }
        double t, l = 0, r = 0;
        for(int i = 0; i < n; ++i)
        for(int j = i+1; j < n; ++j)
        {
            t = (a[0][i].x-a[0][j].x)*(a[0][i].x-a[0][j].x);
            t += (a[0][i].y-a[0][j].y)*(a[0][i].y-a[0][j].y);
            dis[0][i][j] = t;
            r = max(r, sqrt(t));
            
            t = (a[0][i].x-a[1][j].x)*(a[0][i].x-a[1][j].x);
            t += (a[0][i].y-a[1][j].y)*(a[0][i].y-a[1][j].y);
            dis[1][i][j] = t;
            r = max(r, sqrt(t));
            
            t = (a[1][i].x-a[0][j].x)*(a[1][i].x-a[0][j].x);
            t += (a[1][i].y-a[0][j].y)*(a[1][i].y-a[0][j].y);
            dis[2][i][j] = t;
            r = max(r, sqrt(t));
            
            t = (a[1][i].x-a[1][j].x)*(a[1][i].x-a[1][j].x);
            t += (a[1][i].y-a[1][j].y)*(a[1][i].y-a[1][j].y);
            dis[3][i][j] = t;
            r = max(r, sqrt(t));
        }
        while(r-l > eps)
        {
            double mid = (l+r)/2;
            if(jg(mid)) l = mid;
            else r = mid;
        }
        printf("%.2f\n", l+eps);
    }
    return 0;
}

poj-3207 Ikki's Story IV - Panda's Trick

抽象语义，构图求解可行性。

代码：

#include <algorithm>
#include <iostream>
#include <string.h>
#include <vector>
#include <cstdio>
#include <cmath>
using namespace std;
const int maxn = 1005;
const int maxm = 4*maxn*maxn;
struct node {int u, v, next;} edge[maxm];
int no, head[maxn];
int dfn[maxn], low[maxn], index, sta[maxn], top;
bool vis[maxn];
int bel[maxn], cnt;
int n, m;
struct coordinate {int u, v;} a[maxn];
void init()
{
	no = 0;
	memset(head, -1, sizeof head);
	index = 0, top = 0;
	memset(dfn, 0, sizeof dfn);
	memset(vis, 0, sizeof vis);
	cnt = 0;
}
inline void add(int u, int v)
{
	edge[no].u = u; edge[no].v = v;
	edge[no].next = head[u]; head[u] = no++;
}
void tarjan(int u)
{
	dfn[u] = low[u] = ++index;
	sta[++top] = u, vis[u] = 1;
	for(int k = head[u]; k+1; k = edge[k].next)
	{
		int v = edge[k].v;
		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;
		do
		{
			vis[sta[top]] = 0;
			bel[sta[top]] = cnt;
			--top;
		}
		while(sta[top+1] != u);
	}
}
bool work()
{
	for(int i = 0; i < m*2; ++i)
	if(!dfn[i]) tarjan(i);
	for(int i = 0; i < m; ++i)
	{
		if(bel[i*2] == bel[i*2+1])
		return 0;
	}
	return 1;
}
void mapping()
{
	for(int i = 0; i < m; ++i)
	{
		scanf("%d %d", &a[i].u, &a[i].v);
		if(a[i].u > a[i].v) swap(a[i].u, a[i].v);
		for(int j = 0; j < i; ++j)
		{
			if(a[i].u < a[j].u && a[i].v > a[j].u && a[i].v < a[j].v)
			add(i*2, j*2+1), add(i*2+1, j*2),
			add(j*2, i*2+1), add(j*2+1, i*2);
			if(a[j].u < a[i].u && a[j].v > a[i].u && a[j].v < a[i].v)
			add(i*2, j*2+1), add(i*2+1, j*2),
			add(j*2, i*2+1), add(j*2+1, i*2);
		}
	}
}
int main()
{
	//freopen("in.txt", "r", stdin);
	while(scanf("%d %d", &n, &m) != EOF)
	{
		init();
		mapping();
		if(work()) puts("panda is telling the truth...");
		else puts("the evil panda is lying again");
	}
	return 0;
}

poj-2296 Map Labeler

二分建图+可行性判断

只说一下哪几个冲突吧：同时不选，必选某点。

代码：

#include <algorithm>
#include <iostream>
#include <string.h>
#include <vector>
#include <cstdio>
using namespace std;
const int maxn = 205;
const int maxm = 4*maxn*maxn;
struct node {int u, v, next;} edge[maxm];
int no, head[maxn];
int dfn[maxn], low[maxn], _index, sta[maxn], top;
bool vis[maxn];
int bel[maxn], cnt;
int t, n;
struct coordinate {int x, y;} a[maxn];
void init()
{
	no = 0;
	memset(head, -1, sizeof head);
	_index = 0, top = 0;
	memset(dfn, 0, sizeof dfn);
	memset(vis, 0, sizeof vis);
	cnt = 0;
}
inline void add(int u, int v)
{
	edge[no].u = u; edge[no].v = v;
	edge[no].next = head[u]; head[u] = no++;
}
void tarjan(int u)
{
	dfn[u] = low[u] = ++_index;
	sta[++top] = u, vis[u] = 1;
	for(int k = head[u]; k+1; k = edge[k].next)
	{
		int v = edge[k].v;
		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;
		do
		{
			vis[sta[top]] = 0;
			bel[sta[top]] = cnt;
			--top;
		}
		while(sta[top+1] != u);
	}
}
bool work()
{
	for(int i = 0; i < n*2; ++i)
	if(!dfn[i]) tarjan(i);
	for(int i = 0; i < n; ++i)
	{
		if(bel[i*2] == bel[i*2+1])
		return 0;
	}
	return 1;
}
void mapping(int k)
{
	for(int i = 0; i < n; ++i)
	for(int j = 0; j < i; ++j)
	{
		if(abs(a[i].x-a[j].x) >= k) continue;
		if(a[i].y == a[j].y)
		add(i*2, j*2+1), add(j*2, i*2+1), add(i*2+1, j*2), add(j*2+1, i*2);
		if(a[i].y > a[j].y && a[i].y-a[j].y < k)
		add(i*2+1, i*2), add(j*2, j*2+1);
		if(a[j].y > a[i].y && a[j].y-a[i].y < k)
		add(j*2+1, j*2), add(i*2, i*2+1);
		if(a[i].y-a[j].y >= k && a[i].y-a[j].y < 2*k)
		add(i*2+1, j*2+1), add(j*2, i*2);
		if(a[j].y-a[i].y >= k && a[j].y-a[i].y < 2*k)
		add(j*2+1, i*2+1), add(i*2, j*2);
	}
}
bool jg(int k)
{
	init();
	mapping(k);
	return work();
}
int main()
{
	for(scanf("%d", &t); t--;)
	{
		scanf("%d", &n);
		for(int i = 0; i < n; ++i)
		scanf("%d %d", &a[i].x, &a[i].y);
		int l = 1, r = 20000;
		while(l <= r)
		{
			int mid = (l+r)>>1;
			if(jg(mid)) l = mid+1;
			else r = mid-1;
		}
		printf("%d\n", r);
	}
	return 0;
}

像刷kb菊苣的题一样也写点题外话，区域赛前2-SAT就做到这儿了，其实只要能将语义抽象出来2-SAT问题，也能抽象出所有的冲突，2-SAT就很好做了。实力还得再提高啊，路还得走...

继续加油~

2-SAT 题目整理

继续阅读

poj2749 Building roads 2-sat

POJ 3683 - Priest John's Busiest Day(2-SAT)

poj3678 Katu Puzzle 【解法二】

[hdu-1814] Peaceful Commission题解

poj3683Priest John's Busiest Day【2-sat二选一输出】 hdu1814Peaceful Commission【2-SAT】输出最小解 uva1146Now or later飞机调度【2-SAT】入门

codeforces round 400 D The Door Problem 2-SAT

[2-SAT] Codeforces 668E #348 (VK Cup 2016 Round 2, Div. 1 Edition) E. Little Artem and 2-SAT

Party 【2-sat入门】+【scc 判断解存在】

2-SAT点击打开链接序言概念算法解释模型题目

POJ 3905 Perfect Election 2-sat判断可行解

Light OJ 1407 - Explosion 【2-sat之 3布尔变量的处理 — 枚举所有状态判断是否存在可行解 + 反向输出可行解】【好题】InputOutputSample InputOutput for Sample InputNote

poj 2723 2-SAT

【UVALive】6776 2014WorldFinal G Metal Processing Plant【2-sat——bitset优化kosaraju求scc】

【ybt金牌导航3-6-5】【luogu P3209】平面图 / 平面图判定平面图 / 平面图判定

[bzoj1997][Hnoi2010]平面图判定——2-SAT+平面图定理