문제를 읽어보시면 대 환장 파티입니다.
여러 부부가 모이는 파티에 그 사이에 수많은 불륜이…
두 가지 조건에 맞춰서 자리를 배정해주시면 됩니다.
한 부부의 남편과 아내는 서로 반대편에 착석
보람이는 철승이가 있는 쪽만 보기 때문에 철승이가 앉은 줄에는 불륜 관계 x
철승이가 앉은 쪽에 불륜 관계가 있으면 안 되고 보람이 쪽에는 있어도 됩니다.
철승이가 앉은 쪽을 0이라 하고 보람이 쪽을 1이라 하면
\[(a \vee b) \wedge (c \vee d) \wedge (e \vee f)\]괄호 안에 있는 두 사람이 불륜 관계라고 한다면 이 식이 1이 된다면 철승이 쪽에 불륜 관계를 없앨 수 있습니다.
괄호 안에 두 사람 중 한 명이라도 1이 된다면 철승이 쪽에 둘 다 앉지 않기 때문입니다.
그리고 한 부부는 서로 반대쪽에 앉아야 하기 때문에 부부 관계는 a 와 ~a로 하겠습니다.
그렇게 되면 이 문제는 2-SAT으로 풀 수 있습니다.
보람이가 앉아 있는 자리가 1이어야 저 식이 성립했을 때 답이 나올 수 있으므로 보람이를 x라 한다면
\(x \vee x\)
도 식에 추가하시면 됩니다.
SCC를 얻은 다음에 한 부부가 같은 SCC 면 “bad luck” 출력!
아니면 가능한 경우이므로 먼저 SCC로 묶인 사람이 0 그다음은 1이라고 생각합니다.
2-SAT - 4 문제와 동일하게 하면 됩니다.
여러 번 WA여서 고생 좀 했습니다…
제 경우를 말씀드리면 철승이가 불륜을 당연히 안 할 줄 알았는데 설마 했는데 불륜을 할 수 있네요…
내로남불… 제정신은 아닌 것 같습니다.
또 한 번은 줄바꿈을 안 해서 틀렸…
#include <bits/stdc++.h>
#define FIO ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define FOR(a,b,c) for(int a = (b); a <= (c); a++)
#define RFOR(a,b,c) for(int a = (b); a >= (c); a--)
#define MAX 65
using namespace std;
typedef vector <int> vi;
typedef vector <vi> vvi;
int main() {
FIO;
while (1) {
int n, m; cin >> n >> m;
if (!n && !m) break;
vvi adj(MAX);
vi finish(MAX), dfsn(MAX), cpn(MAX);
int cnt = 0, z = 0;
stack <int> st;
auto ndx = [&](int a, int b) {return abs(a) * 2 - (b ? (a > 0) : (a < 0)); };
while (m--) {
int a = 0, b = 0;
string s1, s2; cin >> s1 >> s2;
FOR(i, 0, s1.length() - 2) a = a * 10 + (s1[i] - '0');
FOR(i, 0, s2.length() - 2) b = b * 10 + (s2[i] - '0');
a++, b++;
if (s1[s1.length() - 1] == 'w') a = -a;
if (s2[s2.length() - 1] == 'w') b = -b;
adj[ndx(a, 1)].push_back(ndx(b, 0));
adj[ndx(b, 1)].push_back(ndx(a, 0));
}
adj[ndx(1, 0)].push_back(ndx(1, 1));
function <int(int)> get_scc = [&](int now) {
int ret = dfsn[now] = ++cnt;
st.push(now);
for (int next : adj[now]) {
if (!dfsn[next]) ret = min(ret, get_scc(next));
else if (!finish[next]) ret = min(ret, dfsn[next]);
}
if (ret == dfsn[now]) {
while (1) {
int tp = st.top(); st.pop();
finish[tp] = 1;
cpn[tp] = z;
if (tp == now) break;
}
z++;
}
return ret;
};
FOR(i, 1, 2 * n)
if (!dfsn[i]) get_scc(i);
int chk = 1;
FOR(i, 1, n) if (cpn[ndx(i, 0)] == cpn[ndx(i, 1)]) chk = 0;
if (!chk) cout << "bad luck";
else FOR(i, 2, n)
cout << i - 1 << ((cpn[ndx(i, 0)] < cpn[ndx(i, 1)]) ? 'h' : 'w') << ' ';
cout << '\n';
}
return 0;
}