【bzoj4945】[Noi2017]游戏（搜索+2-sat）

bzoj

洛谷

题意：

现在有$a,b,c$三种车，每个赛道可能会存在限制：$a$表示不能选择$a$类型的赛车，$b,c$同理；$x$表示该赛道不受限制，但$x$类型的个数$$d\leq 8$。
同时赛道之间还存在$m$条关系，每个关系用$(i\ h_i\ j\ h_j)$表示，意味着若在第$i$个赛道选择$h_i$类的车，则必须在$j$赛道选择$h_j$类的车。
现在问是否存在一种合法安排赛车的方案，有则任意输出一种方案，没有则输出$-1$。

思路：

$x$类赛道个数较少，我们先不考虑其存在，那么问题变为了一个存在一些限制条件的$2-sat$问题，我们先来解决这个问题。
对于合法的限制，直接连边即可；若$i$赛道不能有$h_i$，因为我们本来就不考虑$h_i$的存在（2-sat问题），那么我们直接无视当前的限制；若$j$赛道不能有$h_j$，此时表示不能选$h_i$，那么连边$h_i\rightarrow h_i'$即可。
然后考虑$x$类赛道，因为个数很少，所以我们可以直接$3^d$枚举选择哪些情况，复杂度变为$O(3^dn)$。
然后这里有个特别巧妙的想法，就是正难则反，我们考虑枚举不选哪个，那么$x$类赛道也变成了某类具体的赛道。首先问题处理上方便了许多，统一为$2-sat$问题；其次，复杂度将为$2^d$，因为假设我们当前不选$a$，那么可以选择$b,c$，不选$b$，那么可以选择$a,c$，这样可以覆盖所有的情况了。

所以通过$2^d$枚举，问题转换为了一个带限制$2-sat$问题。感觉还是挺巧妙的，上午有点累没好好想，可惜了QAQ

代码如下：

/*

 * Author:  heyuhhh

 * Created Time:  2019/12/2 11:21:16

 */

#include <iostream>

#include <algorithm>

#include <cstring>

#include <vector>

#include <cmath>

#include <set>

#include <map>

#include <queue>

#include <iomanip>

#define MP make_pair

#define fi first

#define se second

#define sz(x) (int)(x).size()

#define all(x) (x).begin(), (x).end()

#define INF 0x3f3f3f3f

#define Local

#ifdef Local

  #define dbg(args...) do { cout << #args << " -> "; err(args); } while (0)

  void err() { std::cout << '\n'; }

  template<typename T, typename...Args>

  void err(T a, Args...args) { std::cout << a << ' '; err(args...); }

#else

  #define dbg(...)

#endif

void pt() {std::cout << '\n'; }

template<typename T, typename...Args>

void pt(T a, Args...args) {std::cout << a << ' '; pt(args...); }

using namespace std;

typedef long long ll;

typedef pair<int, int> pii;

//head

const int N = 1e5 + 5, M = 1e5 + 5;

int n, m, d;

char s[N], t[N];

int pos[N], tot;

char x[N];

struct Edge {

    int i, j;

    char pi, pj;

}e[M];

vector<int> G[N], rG[N], vs;

int used[N], bel[N];

void adde(int from, int to) {

    G[from].push_back(to);

    rG[to].push_back(from);

}

void dfs(int v) {

    used[v] = true;

    for(int u: G[v]) {

        if(!used[u])

            dfs(u);

    }

    vs.push_back(v);

}

void rdfs(int v, int k) {

    used[v] = true;

    bel[v] = k;

    for(int u: rG[v])

        if(!used[u])

            rdfs(u, k);

}

int scc() {

    memset(used, 0, sizeof(used));

    vs.clear();

    for(int v = 1; v <= 2 * n; ++v)

        if(!used[v]) dfs(v);

    memset(used, 0, sizeof(used));

    int k = 0;

    for(int i = (int) vs.size() - 1; i >= 0; --i)

        if(!used[vs[i]]) rdfs(vs[i], k++);

    return k;

}

void work() {

    for(int i = 1; i <= 2 * n; i++) G[i].clear(), rG[i].clear();

    for(int i = 1; i <= n; i++) {

        if(t[i] == 'a') {

            x[i] = 'b';

            x[i + n] = 'c';

        } else if(t[i] == 'b') {

            x[i] = 'a';

            x[i + n] = 'c';

        } else {

            x[i] = 'a';

            x[i + n] = 'b';

        }

    }

    for(int i = 1; i <= m; i++) {

        int u = e[i].i, v = e[i].j;

        char pi = e[i].pi, pj = e[i].pj;

        if(t[u] == pi) continue;

        if(t[v] == pj) {

            if(x[u] == pi) adde(u, u + n);

            else adde(u + n, u);

        } else {

            if(x[u] == pi) {

                if(x[v] == pj) adde(u, v), adde(v + n, u + n);

                else adde(u, v + n), adde(v, u + n);

            } else {

                if(x[v] == pj) adde(u + n, v), adde(v + n, u);

                else adde(u + n, v + n), adde(v, u);

            }

        }

    }

    scc();

    for(int i = 1; i <= n; i++) {

        if(bel[i] == bel[i + n]) return;

    }

    for(int i = 1; i <= n; i++) {

        if(bel[i] > bel[i + n]) {

            printf("%c", x[i] - 'a' + 'A');

        } else printf("%c", x[i + n] - 'a' + 'A');

    }

    cout << '\n';

    exit(0);

}

void go(int cur) {

    if(cur > tot) {

        work(); return;

    }

    t[pos[cur]] = 'a'; go(cur + 1);

    t[pos[cur]] = 'b'; go(cur + 1);

}

void run(){

    scanf("%s", s + 1);

    for(int i = 1; i <= n; i++) {

        t[i] = s[i];

        if(s[i] == 'x') pos[++tot] = i;

    }

    cin >> m;

    for(int i = 1; i <= m; i++) {

        int u, v;

        char pi, pj;

        scanf("%d %c %d %c", &u, &pi, &v, &pj);

        pi = pi - 'A' + 'a';

        pj = pj - 'A' + 'a';

        e[i] = Edge {u, v, pi, pj};

    }

    go(1);

    cout << -1 << '\n';

}

int main() {

    while(cin >> n >> d) run();

    return 0;

}

巴特西

【bzoj4945】[Noi2017]游戏（搜索+2-sat）

最新文章

热门文章