CF1697F Too Many Constraints 题解

· · 题解

看起来就像 2-sat。但每个点的取值为 1\sim k，似乎是 k-sat。

注意到 k 比较小，可以想到把每个点 p 拆成 k 个 bool 变量，其中第 i 个 bool 变量 X_{p,i} 表示 a_p 是否 \le i。

显然此时要连接 T_{p,i}\to T_{p_,i+1}（满足变量含义）和 T_{p, i} \to T_{p-1, i}（满足单调不降）。还有它们的反边（u\to v 的反边指 v' \to u'）。

至于为什么不拆成 X_{p,i} 表示 a_p 是否 =i，见此。

取值型问题一般状态设计是变量 x\ge k。形如 x=k 的状态设计不好做，因为默认了 x 的若干个状态中必须有且只有一个为 \text{True}，然而实际建图中无法建出这样的限制条件，也可能是我太菜了所以建不出。

那么对于题目中给出的若干种限制：

最后注意一下上面的下标显然会越界，越界的时候特判一下即可。如 a_i+a_j\le k-2，暗含 a_i, a_j\le k-3。

然后你就做完了。（还挺套路的，除了建图真的麻烦

丑陋的代码：

// Problem: F. Too Many Constraints
// From: Codeforces - Educational Codeforces Round 130 (Rated for Div. 2)
// URL: https://codeforces.com/contest/1697/problem/F
// Time: 2022-06-12 22:35
// Author: lingfunny

#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int mxn = 2e4+10, mxz = 20*mxn;

int n, m, k, tot;
vector <int> G[mxz];
#define _(x) (x > tot ? x - tot : x + tot)
inline void add(int u, int v) { G[u].emplace_back(v);
// int u_ = u > tot ? u - tot : u, v_ = v > tot ? v - tot: v;
// printf("(%d, %d) %c -> (%d, %d) %c\n", u_%n?u_%n:n, (u_%n?u_/n:(u_-1)/n)+1, u>tot?'F':'T',
// v_%n?v_%n:n, (v_%n?v_/n:(v_-1)/n)+1, v>tot?'F':'T');
}
inline void dadd(int u, int v) { add(u, v), add(_(v), _(u)); }
int low[mxz], dfn[mxz], dfc, in[mxz], stk[mxz], top, scc[mxz], cnt;
void tarjan(int u) {
    low[u] = dfn[u] = ++dfc, in[stk[++top] = u] = 1;
    for(int v: G[u]) {
        if(!dfn[v]) tarjan(v), low[u] = min(low[u], low[v]);
        else if(in[v]) low[u] = min(low[u], dfn[v]);
    }
    if(dfn[u] == low[u] && ++cnt) do scc[stk[top]] = cnt, in[stk[top]] = 0; while(stk[top--] != u);
}

inline void solve() {
    scanf("%d%d%d", &n, &m, &k);
    tot = n * k;
    // printf("n = %d, m = %d, k = %d\n", n, m, k);
    for(int i = 1; i <= tot*2; ++i) dfn[i] = 0, vector <int> ().swap(G[i]);
    dfc = top = cnt = 0;
    for(int p = 1; p <= n; ++p) for(int i = 1; i < k; ++i) dadd(p+(i-1)*n, p+i*n);
    for(int p = 2; p <= n; ++p) for(int i = 1; i <= k; ++i) dadd(p+(i-1)*n, p-1+(i-1)*n);
    add(2*tot, tot);
    // puts("END");
    for(int op, i, j, x; m--;) {
        scanf("%d", &op);
        if(op == 1) {
            scanf("%d%d", &i, &x);
            if(x == 1) add(i, _(i));
            else dadd(i+(x-1)*n, i+(x-2)*n);
        } else {
            scanf("%d%d%d", &i, &j, &x);
            if(op == 2) {
                if(x-1 < k)
                add(_(i+(x-2)*n), i+(x-2)*n),
                add(_(j+(x-2)*n), j+(x-2)*n);
                for(int p = 1; p <= k; ++p) {
                    int oth = x - p - 1;
                    if(oth >= 1 && oth <= k)
                    dadd(_(i+(p-1)*n), j+(oth-1)*n),
                    dadd(_(j+(p-1)*n), i+(oth-1)*n);
                }
            } else {
                if(x-k > 1)
                add(i+(x-k-2)*n, _(i+(x-k-2)*n)),
                add(j+(x-k-2)*n, _(j+(x-k-2)*n));
                for(int p = 1; p <= k; ++p) {
                    int oth = x - p - 1;
                    if(oth >= 1 && oth <= k)
                    dadd(i+(p-1)*n, _(j+(oth-1)*n)),
                    dadd(j+(p-1)*n, _(i+(oth-1)*n));
                }
            }
        }
    }
    for(int i = 1; i <= 2*tot; ++i) if(!dfn[i]) tarjan(i);
    for(int i = 1; i <= tot; ++i) if(scc[i] == scc[i+tot]) return puts("-1"), void();
    for(int i = 1; i <= n; ++i) {
        for(int p = 0; p < k; ++p) if(scc[i+p*n] < scc[_(i+p*n)]) { printf("%d%c", p+1, " \n"[i==n]); break; }
    }
}

int main() {
    int tt;
    scanf("%d", &tt);
    while(tt--) solve();
}