当前位置: 代码迷 >> 综合 >> POJ 3648 2-sat 输出解
  详细解决方案

POJ 3648 2-sat 输出解

热度:63   发布时间:2024-01-13 17:56:57.0

这题的题意稍不留神就会看错,注意那个keep ...from 是啥意思

所以新娘看不见本排的情况,只能看见对面,要求不能看见不正常关系的一对。并且夫妇不能同时坐在一边。

很明显的模型了,由于新娘看的是对面的情况,所以就需要对新娘对面的人来分析建图,n对夫妇是2 *n个点, n对夫妇每对夫妇只能挑一个到新娘对面坐下,这很符合2-sat的初始的状态。然后又有一些不正常关系,就需要分别建图了。 并且初始时应该是丈夫坐在新娘对面的,新娘编号为0,丈夫为1的话,必须加一条(0,1)的边表示丈夫必然坐在对面。

建完图后缩点,判断有没有解后,需要建新图,即缩点后的逆序图,然后进行拓扑排序,染色。 注意,我们需要将每对夫妻两者各自代表的强连通分量映射起来,表示这两个强连通分量是不可以在一块的。这样在新图染色的时候,每染到一个点,根据刚才存储的映射将对应的点染为别的颜色。最后输出解时,找跟新娘同色的解即为和新娘同一排的人。



#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#define MAXN 5005
#define MAXM 50005
#define INF 1000000000
using namespace std;
vector<int>g[MAXN], dag[MAXN];
int n, m;
int dfn[MAXN], low[MAXN], instack[MAXN];
int scc, index, fa[MAXN], ha[MAXN], ind[MAXN];
int color[MAXN];
stack<int>st;
queue<int>q;
void init()
{scc = index = 0;for(int i = 0; i < 2 * n; i++)g[i].clear(), dag[i].clear();memset(instack, 0, sizeof(instack));memset(dfn, 0, sizeof(dfn));while(!st.empty()) st.pop();while(!q.empty()) q.pop();memset(ind, 0, sizeof(ind));memset(color, 0, sizeof(color));
}
void tarjan(int u)
{dfn[u] = low[u] = ++index;instack[u] = 1;st.push(u);int size = g[u].size(), v;for(int i = 0; i < size; i++){v = g[u][i];if(!dfn[v]){tarjan(v);low[u] = min(low[u], low[v]);}else if(instack[v]) low[u] = min(low[u], dfn[v]);}if(dfn[u] == low[u]){scc++;do{v = st.top();st.pop();instack[v] = 0;fa[v] = scc;}while(v != u);}
}
void buildDag()
{for(int u = 0; u < 2 * n; u++){int size = g[u].size();for(int i = 0; i < size; i++){int v = g[u][i];if(fa[u] != fa[v]) dag[fa[v]].push_back(fa[u]), ind[fa[u]]++;}}
}
void topsort()
{for(int i = 1; i <= scc; i++)if(ind[i] == 0) q.push(i);while(!q.empty()){int u = q.front();q.pop();int size = dag[u].size();if(!color[u]) color[u] = 1, color[ha[u]] = 2;for(int i = 0; i < size; i++){int v = dag[u][i];ind[v]--;if(ind[v] == 0) q.push(v);}}
}
void solve()
{for(int i = 0; i < 2 * n; i++)if(!dfn[i]) tarjan(i);for(int i = 0; i < n; i++)if(fa[2 * i] == fa[2 * i + 1]){puts("bad luck");return;}else ha[fa[2 * i]] = fa[2 * i + 1], ha[fa[2 * i + 1]] = fa[2 * i];buildDag();topsort();for(int i = 2; i < 2 * n; i += 2)if(color[fa[i]] == color[fa[0]]) printf("%d%c ", i / 2, 'w');else printf("%d%c ", i / 2, 'h');printf("\n");
}
int main()
{char c1, c2;int x, y, a0, b0, a1, b1;while(scanf("%d%d", &n, &m) != EOF){if(n == 0 && m == 0) break;init();while(m--){scanf("%d%c %d%c", &x, &c1, &y, &c2);if(c1 == 'h') a0 = 2 * x, a1 = 2 * x + 1;else a0 = 2 * x + 1, a1 = 2 * x;if(c2 == 'h') b0 = 2 * y, b1 = 2 * y + 1;else b0 = 2 * y + 1, b1 = 2 * y;g[a1].push_back(b0);g[b1].push_back(a0);}g[0].push_back(1);solve();}return 0;
}