# UVA1086 The Ministers' Major Mess

## 0.题目描述

**题面:** [链接](https://uva.onlinejudge.org/external/10/p1086.pdf)

大致意思是有 \\(B\\) 个方案和 \\(M\\) 个人，每个人可以对 \\(k(k \le 4)\\) 个方案投票，每一票要么支持要么反对。每个人满意当且仅当他一半以上的投票被满足，问每个方案应通过 ( `y` ) 还是否决 ( `n` )，或者既可以通过也可以否决 ( `?` )，才能使得每一个人对最终的结果满意。如果不存在一种使得所有人满意的结果，输出 `impossible` 。

## 1.分析 + 代码

对于每一个方案只有通过和否决两种状态，每一个人的投票相当于是限制条件，这道题明显是一个 **2-SAT** 的问题。

### 1.1 建边

将每个方案拆成两个点 `true` 和 `false`，分别表示通过和否决，然后考虑限制条件。

由于 \\(k\\) 的范围很小，我们可以对 \\(k\\) 的取值进行分类讨论。

- \\( k \le 2\\) 

  \\(k = 1\\) 时需满足的票数大于 \\(0.5\\)，即 \\(1\\) ， \\(k = 2\\) 时需满足的票数大于 \\(1\\) ，即 \\(2\\) 。

  所以如果一个人的 \\(k\\) 满足 \\(k \le 2\\) ，他投的所有票都将得到满足。

  转换到图上就是将相应的方案的相反结果向其投票的结果建一条边，这样投票就必须被满足。 


- \\(3 \le k \le 4\\)

  \\(k = 3\\) 时需满足的票数大于 \\(1.5\\) ，即 \\(2\\) 或 \\(3\\) ， \\(k = 4\\) 时需满足的票数大于 \\(2\\) ，即 \\(3\\) 或 \\(4\\) 。

  所以如果一个人的 \\(k\\) 满足 \\(3 \le k \le 4\\)，他投的票至多有一个得不到满足。也就是说，如果有一票得不到满足，那么其他所有的票就必须全部满足。

  转换到图上就是将每一票的相反的结果向其余所有票的结果分别建一条边。

为了方便处理各种状态，可以写一个函数导出相应点的下标。

```cpp
// 1~n 为 false(否决) n + 1 ~ 2n 为 true(通过)
int f(bool op, int p) {
	return p + op * n; // op为标记，通过为true，否决为false
}
```

建边部分代码：

```cpp
struct Query {
	bool op;
	int p;
} q[4]; // 存投票情况

bool ed[N][N]; // 邻接矩阵
 
// ...main...
if (k <= 2) {
    // 全部通过
    for (int j = 0; j < k; ++j) {
        ed[f(!q[j].op, q[j].p)][f(q[j].op, q[j].p)] = true;
    }
}
else {
    // 如果第j个被否决，其余(k - 1)个必须通过
    for (int j = 0; j < k; ++j) {
        for (int l = 0; l < k; ++l) {
            if (j == l) continue;
            ed[f(!q[j].op, q[j].p)][f(q[l].op, q[l].p)] = true;
        }
    }
}
```

### 1.2 输出方案

如果只输出一种可行方案，那么很简单，取每个方案的 `true` 点和 `false` 点中拓扑序较大的即可。

一种可行的方案是直接在图上跑一遍 tarjan 求出每个点所在的强连通分量的编号， 输出所在强连通分量的编号较小的即可（ tarjan 得到的编号的顺序是拓扑逆序）。

但是这道题存在一个 `?` 的情况，表示选 `true` 和 `false` 均可行，明显上面这个方法无法解决，考虑一下其他思想。

#### 1.2.1 枚举

可以考虑先跑一遍 tarjan 得到一组可行解然后依次验证每一个方案是否可以取反，如果可以就改成 `?` ，大致流程如下：

1. 跑一遍 tarjan 得到一组可行解。
2. 遍历可行解的每一个位置。
3. 对于每一个位置，临时建一条反向的边，限制该位置必须选相反的结果。
4. 再跑一遍 tarjan，验证是否仍然可行。
5. 如果可行，改为 `?` ， 否则不变。
6. 删掉临时边，继续尝试下一个位置。

跑完一轮后，就可以得到答案，时间复杂度是 \\(O(n ^ 3)\\)(邻接矩阵)。

[参考代码](https://vjudge.net/solution/38385081/xbB6UvWNqNy7rQSx2yHz)

#### 1.2.2 传递闭包（Floyd求图的连通性）

进一步思考，设一个下标为 \\(p\\) 方案 `true` 点为  \\(p + n\\) ，`false` 点为 \\(p\\) 。

- 若 \\(p\\) 能走到 \\(p + n\\) 且 \\(p + n\\) 不能走到 \\(p\\) ，那么这个方案只能为 `true` 。
- 若 \\(p + n\\) 能走到 \\(p\\) 且 \\(p\\) 不能走到 \\(p + n\\) ，那么这个方案只能为 `false` 。
- 若 \\(p\\) 不能走到 \\(p + n\\) 且 \\(p + n\\) 不能走到 \\(p\\) ，那么这个方案可以为 `true` 也可以为 `false` ，即题中 `?` 。
- 若 \\(p\\) 能走到 \\(p + n\\) 且 \\(p + n\\) 能走到 \\(p\\) ，那么这个方案既不可以为 `true` 也不可以为 `false` ，即 `impossible` 。

所以直接对建好的图跑一遍传递闭包即可，时间复杂度也是 \\(O(n ^ 3)\\) ，但由于不能快速判断是否可行，所以整体速度比 tarjan 慢很多，~~但是代码短呀~~。

```cpp
for (int k = 1; k <= n * 2; ++k) {
    for (int i = 1; i <= n * 2; ++i) {
        for (int j = 1; j <= n * 2; ++j) {
            if (i == j) continue;
            else ed[i][j] |= ed[i][k] & ed[k][j]; // i与k连通且k与j连通则i与j连通
        }
    }
}
```

# Ac Code

传递闭包只有 82 行，很清爽。

```cpp
#include <cstdio>
#include <cstring>
#include <iostream>

using namespace std;

const int N = 210;

struct Query {
	bool op; // true为通过, false为否决
	int p; // 相应方案的下标
} q[4]; // 存投票情况

bool ed[N][N]; // 邻接矩阵
char ans[N]; // 存答案
int n, m;

// 1~n 为 false(否决) n + 1 ~ 2n 为 true(通过)
int f(bool op, int p) {
	return p + op * n; // op为标记，通过为true，否决为false
}

int main() {
	int T = 0;
	while (scanf("%d%d", &n, &m), n && m) {
		T++;
        // 记得初始化
		memset(ed, 0, sizeof(ed));
		memset(ans, 0, sizeof(ans));
		for (int i = 1; i <= m; ++i) {
			int k;
			scanf("%d", &k);
			for (int j = 0; j < k; ++j) {
				char s[2];
				scanf("%d%s", &q[j].p, s);
				q[j].op = (s[0] == 'y');
			}
			if (k <= 2) {
                // 全部通过
				for (int j = 0; j < k; ++j) {
					ed[f(!q[j].op, q[j].p)][f(q[j].op, q[j].p)] = true;
				}
			}
			else {
                // 如果第j个被否决，其余(k - 1)个必须通过
				for (int j = 0; j < k; ++j) {
					for (int l = 0; l < k; ++l) {
						if (j == l) continue;
						ed[f(!q[j].op, q[j].p)][f(q[l].op, q[l].p)] = true;
					}
				}
			}
		}
        // 传递闭包
        for (int k = 1; k <= n * 2; ++k) {
            for (int i = 1; i <= n * 2; ++i) {
                for (int j = 1; j <= n * 2; ++j) {
                    if (i == j) continue;
                    else ed[i][j] |= ed[i][k] & ed[k][j];
                }
            }
        }
		bool valid = true;
		for (int i = 1; i <= n; ++i) {
			if (ed[i][i + n] && ed[i + n][i]) { // impossible
				valid = false;
				break;
			}
			else if (!ed[i][i + n] && !ed[i + n][i]) ans[i] = '?';
			else if (ed[i][i + n]) ans[i] = 'y';
			else ans[i] = 'n';
		}
		printf("Case %d: ", T); // 某憨憨由于没输出Case调了半天
		if (valid)
			for (int i = 1; i <= n; ++i) {
				putchar(ans[i]);
			}
		else
			printf("impossible"); 
		printf("\n");
	}
	return 0;
}
```