洛谷题单指南-连通性问题-P3825 [NOI2017] 游戏
原题链接：https://www.luogu.com.cn/problem/P3825
题意解读：
解题思路：
1、问题分析
对于每种地图a、b、c只支持两种车，因此可以转化为2-SAT问题，但是地图x可以支持任意车，由于x的数量不多，可以暴搜所有的可能，时间复杂度最坏是3^8=6561，对于每一种可能都要跑一次2-SAT，时间复杂度级别为10^5 * 6561 > 10^8，依然不可行。
其实，对于x，并不需要枚举a、b、c三种情况，只需要枚举a、b两种情况，就可以覆盖所有车的方案，因此对于a可以支持B/C两种车，对于b可以支持A/C两种车，综合起来就覆盖到了A、B、C三种车。这样时间复杂度级别在10^5 * 2^8 ≈ 10^7，可行。
2、问题转化
接下来，就要看问题模型如何转化成2-SAT。
设第i场游戏用车对应的节点为p = i 或 ¬p = i + n，
对于地图a，p表示用车B，¬p表示用车C；
对于地图b，p表示用车A，¬p表示用车C；
对于地图c，p表示用车A，¬p表示用车B。
对于四元组 (i,hi,j,hj)，设第i场用车是hi对应节点是u，第j场用车是hj对应的节点是v，节点转换规则为：
对于地图a，用车hi = B对应节点u = i，用车hi = C对应节点u = i + n
对于地图b，用车hi = A对应节点u = i，用车hi = C对应节点u = i + n
对于地图c，用车hi = A对应节点u = i，用车hi = B对应节点u = i + n
如果第i场地图是hi，意味着第i场用车不能是hi，因此可以忽略；
如果第j场地图是hj，意味着第j场用车不能是hj，那么当第i用车是hi，肯定无解，可以建立u -> ¬u的有向边，表示矛盾；
如果第i场地图不是hi，当第i场用车hi，必有第j场用车hj，建立u -> v的有向边，同时建立¬v -> ¬u的有向边。
100分代码：
#include <bits/stdc++.h>
using namespace std;
const int N = 100005, M = 300005;
int head[N], to[M], nxt[M], idx;
int dfn[N], low[N], timestamp;
stack<int> stk;
bool vis[N];
int scc[N], cnt;
int n, d, m;
string s;
int id[N], total; //id[i]表示s[i]是s中第几个x
char path[N]; //path[0] ~ path[d-1]是所有x的一种可能的选项排列
struct Require
{
int i;
char hi;
int j;
char hj;
} req[M];
//获取s[pos]的地图
char get(int pos)
{
if(s[pos] == 'x') return path[id[pos]];
else return s[pos];
}
//获取第pos辆车选用c时的节点
int node(int pos, char c)
{
char mp = get(pos);
if(mp == 'a')
{
if(c == 'B') return pos;
else return pos + n;
}
else if(mp == 'b')
{
if(c == 'A') return pos;
else return pos + n;
}
else
{
if(c == 'A') return pos;
else return pos + n;
}
}
//获取第pos辆车，在条件ok时的值
char car(int pos, bool ok)
{
char mp = get(pos);
if(mp == 'a')
{
if(ok) return 'B';
else return 'C';
}
else if(mp == 'b')
{
if(ok) return 'A';
else return 'C';
}
else
{
if(ok) return 'A';
else return 'B';
}
}
//节点取反的节点
int neg(int id)
{
if(id <= n) return id + n;
else return id - n;
}
//建立有向边a->b
void add(int a, int b)
{
to[++idx] = b;
nxt[idx] = head[a];
head[a] = idx;
}
//根据2-SAT模型建图
void build()
{
for(int k = 1; k <= m; k++)
{
//如果第i场地图是hi，意味着第i场用车不能是hi，因此可以忽略；
if(get(req[k].i) - 32 == req[k].hi) continue;
//如果第j场地图是hj，意味着第j场用车不能是hj，那么当第i用车是hi，肯定无解，可以建立u -> ¬u的有向边，表示矛盾；
if(get(req[k].j) - 32 == req[k].hj)
{
int u = node(req[k].i, req[k].hi);
add(u, neg(u));
continue;
}
//如果第i场地图不是hi，当第i场用车hi，必有第j场用车hj，建立u -> v的有向边，同时建立¬v -> ¬u的有向边。
int u = node(req[k].i, req[k].hi);
int v = node(req[k].j, req[k].hj);
add(u, v), add(neg(v), neg(u));
}
}
//清空数组
void clear()
{
memset(head, 0, sizeof(head));
idx = 0;
memset(dfn, 0, sizeof(dfn));
memset(low, 0, sizeof(low));
memset(scc, 0, sizeof(scc));
cnt = 0;
}
void tarjan(int u)
{
dfn[u] = low[u] = ++timestamp;
stk.push(u);
vis[u] = true;
for(int i = head[u]; i; i = nxt[i])
{
int v = to[i];
if(!dfn[v])
{
tarjan(v);
low[u] = min(low[u], low[v]);
}
else if(vis[v]) low[u] = min(low[u], dfn[v]);
}
if(low[u] == dfn[u])
{
cnt++;
while(true)
{
int t = stk.top(); stk.pop();
vis[t] = false;
scc[t] = cnt;
if(t == u) break;
}
}
}
bool check()
{
bool ok = true;
for(int i = 1; i <= n; i++)
{
if(scc[i] == scc[i + n])
{
ok = false;
break;
}
}
if(!ok)
{
return false;
}
for(int i = 1; i <= n; i++)
{
if(scc[i] < scc[i + n]) cout << car(i, true);
else cout << car(i, false);
}
cout << endl;
return true;
}
//枚举所有x取A或B的排列组合
void dfs(int k)
{
if(k > d)
{
//对于一个排列，执行2-SAT
clear();
build(); //建图
for(int i = 1; i <= 2 * n; i++)
if(!dfn[i])
tarjan(i);
if(check()) exit(0); //找到解则结束程序
return;
}
path[k] = 'a'; dfs(k + 1);
path[k] = 'b'; dfs(k + 1);
}
int main()
{
cin >> n >> d >> s >> m;
s = " " + s; //字符串从1开始
for(int i = 1; i <= m; i++)
cin >> req[i].i >> req[i].hi >> req[i].j >> req[i].hj;
for(int i = 1; i <= s.size(); i++)
if(s[i] == 'x')
id[i] = ++total;
dfs(1);
cout << -1;
return 0;
}