Luogu P4171 [JSOI2010]满汉全席 2-sat

终于搞懂了\(2-sat\)。实际上是个挺简单的东西，像网络流一样关键在于建模。

问题：\(n\)个数\(A\)，可以选择\(0\)和\(1\)，现在给你\(m\)组条件\(A\)，\(B\)，对每个条件要求\(A\)为真或者\(B\)为真。

\(2-sat\)的建图方法：把每一个或条件拆成两个。例如对于条件\(A\) \(or\) \(B\)：

如果\(A\)为假，那么\(B\)必须为真。（\(A_false\) \(->\) \(B_true\)）
如果\(B\)为假，那么\(A\)必须为真。（\(B_false\) \(->\) \(A_true\)）

即一条边代表一条指向条件，选择一个点就代表着同时要选择它的闭合子图中的其他点。容易知道：如果存在一个圈，其中同时包含\(x_false\)和\(x_true\)，那么取值选择无解。这个过程可以用\(Tarjan\)求\(scc\)来做。

可行解的构造：把原图缩成若干\(scc\)后，对每个条件\(A\)，我们优先选对应点拓扑序比较大的那个值，这样就可以向着最容易出解的方向选择。（选择一个点就代表着同时要选择它的闭合子图中的其他点。）

特定解的构造：暴力。此问题\(np\)完全。

#include <bits/stdc++.h>

using namespace std;

const int N = 200 + 5;

const int M = 2000 + 5;

struct Graph {

	int cnt, head[N];

	struct Edge {

		int nxt, to;

	}e[M];

	void clear () {

		cnt = -1;

		memset (head, -1, sizeof (head));

	}

	void add_edge (int u, int v) {

		e[++cnt] = (Edge) {head[u], v}; head[u] = cnt;

	}

	stack <int> sta;

	int _dfn, _sccid;

	int inq[N], dfn[N], low[N], sccid[N];

	void Tarjan (int u) {

		dfn[u] = low[u] = ++_dfn;

		inq[u] = true; sta.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 (inq[v]) {

				low[u] = min (low[u], dfn[v]);

			}

		}

		if (dfn[u] == low[u]) {

			int tmp; ++_sccid;

			do {

				tmp = sta.top ();

				inq[tmp] = false;

				sccid[tmp] = _sccid;

				sta.pop ();

			}while (tmp != u);

		}

	}

	void get_scc (int n) {

		_dfn = _sccid = 0;

		memset (inq, 0, sizeof (inq));

		memset (dfn, 0, sizeof (dfn));

		for (int i = 1; i <= n; ++i) {

			if (!dfn[i]) Tarjan (i);

		}

	}

}G;

int T, n, m;

int node (int x, int t) {

	return n * t + x;

}

int main () {

	// freopen ("data.in", "r", stdin);

	cin >> T;

	while (T--) {

		cin >> n >> m; G.clear ();

		for (int i = 1; i <= m; ++i) {

			static int u, v, t1, t2;

			while (!isalpha (t1 = getchar ())); cin >> u;

			while (!isalpha (t2 = getchar ())); cin >> v;

			t1 = t1 == 'm' ? 0 : 1;

			t2 = t2 == 'm' ? 0 : 1;

			G.add_edge (node (u, !t1), node (v, t2));

			G.add_edge (node (v, !t2), node (u, t1));

		}

		G.get_scc (n << 1);

		bool succ = true;

		for (int i = 1; i <= n; ++i) {

			if (G.sccid[node (i, 0)] == G.sccid[node (i, 1)]) {

				succ = false; break;

			}

		}

		puts (succ ? "GOOD" : "BAD");

	}

}

巴特西

Luogu P4171 [JSOI2010]满汉全席 2-sat

最新文章

热门文章