题意简述
\(\qquad\)有几组要求,由二元状态表示 \((ca, cb)\),其中 \(a, b\)表示的是菜品,\(c\)表示的是样式,当 \(c\) 为 m
时是满式,为h
时是汉式。问是否有一种方案,使得每组要求至少可以满足其中一个要求。
解题思路
\(\qquad\)我们将一个点拆为两个,用 \(2i\)表示满式第 \(i\) 种,用 \(2i + 1\)表示汉式第 \(i\) 种。
\(\qquad\)由于每个选手可以做出 \(n\) 道菜,而总共的菜数只有 \(2n\) 中,那么很容易可以推出每种菜要么做满式,要么做汉式。
\(\qquad\)接下来我们对这个题目进行分类讨论:
\(\qquad\large 1.\ \ \large (m_i, m_j)\) 由于至少满足一种情况,那另一种不满足的时候前一种就应该满足,所以可以得到:$$\Large \neg m_i\Rightarrow m_j$$
\[\Large\neg m_j\Rightarrow m_i \]因为不做满式就只能做汉式,所以整理得到:$$\Large h_i\Rightarrow m_j,\ 2i+1\to 2j$$$$\Large h_j\Rightarrow m_i, \ 2j+1\to2i$$
\(\qquad\large 2.(m_i,h_j)\)同理可得$$\Large h_i\Rightarrow h_j,\ 2i+1\to 2j+1$$$$\Large m_j\Rightarrow m_i,\ 2j\to 2i$$
\(\qquad\large 3.(h_i,m_j)\)同理可得$$\Large m_i\Rightarrow m_j,\ 2i\to 2j$$$$\Large h_j\Rightarrow h_i,\ 2j+1\to 2i+1$$
\(\qquad\large 4.(h_i,h_j)\)同理可得$$\Large m_i\Rightarrow h_j,\ 2i\to 2j+1$$$$\Large m_j\Rightarrow h_i,\ 2j\to 2i+1$$
容易发现上述条件关系有一定的奇偶关系,所以可以用 \(xor\) 运算来简化:
u = u * 2 + (t1 == 'h');
v = v * 2 + (t2 == 'h');
add(u ^ 1, v), add(v ^ 1, u);
然后跑 Tarjan
, 如果一个菜满式和汉式在同一个分量里,就无解
代码
#include <iostream>
#include <cstring>
#include <vector>
#define init(x, y) memset(x, y, sizeof x)
using namespace std;
const int N = 2010;
int e[N], ne[N], h[N], idx;
int stmp, dfn[N], low[N];
int ins[N], stk[N], tt;
int n, m, scc_cnt, id[N];
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}
void dfs(int u)
{
dfn[u] = low[u] = ++ stmp;
stk[ ++ tt] = u, ins[u] = 1;
for (int i = h[u]; ~i; i = ne[i])
{
int j = e[i];
if (!dfn[j]) dfs(j);
if (ins[j]) low[u] = min(low[u], low[j]);
}
if (low[u] == dfn[u])
{
int y; ++ scc_cnt;
do {
y = stk[tt -- ], ins[y] = 0;
id[y] = scc_cnt;
} while (y != u);
}
}
int main()
{
int T;
scanf("%d", &T);
while (T -- )
{
init(h, -1), init(dfn, 0);
tt = scc_cnt = idx = 0;
scanf("%d%d", &n, &m);
while (m -- )
{
char t1, t2;
int u, v;
scanf(" %c%d %c%d", &t1, &u, &t2, &v);
u --, v --;
u = u * 2 + (t1 == 'h');
v = v * 2 + (t2 == 'h');
add(u ^ 1, v), add(v ^ 1, u);
}
for (int i = 0; i < 2 * n; i ++ )
if (!dfn[i]) dfs(i);
int flag = 1;
for (int i = 0; i < n && flag; i ++ )
if (id[i * 2] == id[i * 2 + 1]) flag = 0;
puts(flag ? "GOOD" : "BAD");
}
return 0;
}
标签:int,qquad,满汉全席,Large,P4171,2i,2j,Rightarrow
From: https://www.cnblogs.com/StkOvflow/p/17134738.html