CF1438C 题解

Milky_Cat · 2024-11-25 17:10:16 · 题解

前言：和机房初二 Master 大神 duel 的时候做到了这题，看到 2-SAT 标签豁然开朗，结果险胜。

注意到这道题每一个格子都有 +1 和 +0 两种状态，可以对应布尔型变量，自然而然就能想到 2-SAT。

我们不妨考虑如何建图。注意到：

• 如果两个格子相邻且相等，两个格子中至少要有一个是 0，至少要有一个是 1，否则依然相等。

• 如果两个格子相邻且差 1，较小的格子为 0 或者较大的格子为 1，否则这两个格子相等。

于是我们建图跑 Tarjan 就做完了。

#include<bits/stdc++.h>
using namespace std;
int t, n, m, a[105][105];
int dx[] = {0, 1, -1, 0, 0}, dy[] = {0, 0, 0, 1, -1};
int tid(int x, int y){
    return (x - 1) * m + y;
}
bool Invalid(int x, int y){
    if (x < 1 || y < 1 || x > n || y > m)
        return 1;
    else
        return 0;
}
vector<int> G[2000005], SCC[2000005];
int ig[2000005], dfn[2000005], low[2000005], col[2000005], vl[2000005];
int a1, a2, cnt, ign, ans, ccnt;
bool vis[2000005], vvis[2000005];
stack<int> s;
queue<int> q;
void tarjan(int u){
    dfn[u] = low[u] = ++cnt;
    s.push(u);
    vis[u] = 1;
    for (auto &v : G[u]){
        if (!dfn[v]){
            tarjan(v);
            low[u] = min(low[u], low[v]);
        }else if (vis[v])
            low[u] = min(low[u], dfn[v]);
    }
    if (dfn[u] == low[u]){
        ccnt++;
        while (!s.empty()){
            int v = s.top();
            s.pop();
            vis[v] = 0;
            col[v] = ccnt;
            SCC[u].push_back(v);
            if (u == v)
                break;
        }
    }
}
void addedge(int u, int a, int v, int b){
    G[u + n * m * a].push_back(v + n * m * (b ^ 1));
    G[v + n * m * b].push_back(u + n * m * (a ^ 1));
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin >> t;
    while (t--){
        cin >> n >> m;
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++)
                cin >> a[i][j];
        for (int i = 1; i <= ccnt; i++)
            SCC[i].clear();
        for (int i = 1; i <= 2 * n * m; i++){
            G[i].clear();
            vis[i] = 0;
            col[i] = 0;
            low[i] = dfn[i] = 0;
        }
        cnt = ccnt = 0;
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++){
                for (int k = 1; k <= 4; k++){
                    int nx = i + dx[k], ny = j + dy[k];
                    if (Invalid(nx, ny))
                        continue;
                    if (a[nx][ny] == a[i][j]){
                        int u, a, v, b;
                        u = tid(i, j), v = tid(nx, ny);
                        a = 1; b = 1;
                        addedge(u, a, v, b);
                        a = 0; b = 0;
                        addedge(u, a, v, b);
                    }else if (a[nx][ny] == a[i][j] + 1){
                        int u, a, v, b;
                        u = tid(i, j), v = tid(nx, ny);
                        a = 0, b = 1;
                        addedge(u, a, v, b);
                    }else if (a[nx][ny] == a[i][j] - 1){
                        int u, a, v, b;
                        u = tid(i, j), v = tid(nx, ny);
                        a = 1, b = 0;
                        addedge(u, a, v, b);
                    }
                }
            }
        for (int i = 1; i <= 2 * n * m; i++)
            if (!dfn[i])
                tarjan(i);
    //  for (int i = 1; i <= 2 * n * m; i++)
    //      cout << col[i] << " ";
    //  cout << "\n";
        for (int i = 1; i <= n; i++){
            for (int j = 1; j <= m; j++)
                cout << a[i][j] + (col[tid(i, j)] < col[tid(i, j) + n * m]) << " ";
            cout << "\n";
        }
    }
    return 0;
}