solve.cpp

#include <bits/stdc++.h>
#define eb emplace_back

typedef long long ll;
typedef std::vector <int> vector;
const int N = 5000, M = 66666;
const ll mod = 18761890748385299;

struct edge {
    int u, v;
    edge (int u0 = 0, int v0 = 0) : u(u0), v(v0) {}
} e[M];

int R, C, V, E = 0;
int p[N];
int elim[N];
int to[M], first[N], next[M];
int orient[M];

inline void addedge(int u, int v) {
    //  fprintf(stderr, "addedge %d %d\n", u, v);
    e[++E] = edge(u, v), next[E] = first[u], first[u] = E;
    e[++E] = edge(v, u), next[E] = first[v], first[v] = E;
}

inline void split(int id, int &r, int &c) {r = --id / C + 1, c = id % C + 1;}
inline int ancestor(int x) {return p[x] == x ? x : (p[x] = ancestor(p[x]));}
inline bool join(int x, int y) {
    if ((x = ancestor(x)) == (y = ancestor(y))) return true;
    return p[x] = y, false;
}

int posX[N], posY[N];
namespace Planar {
#define ad(x) (((x - 1) ^ 1) + 1)
    int F = 0;
    int belF[M], remain[M], que[M];
    vector face[M];

    inline bool judge(int A, int B, int C, int D) {
        if(posX[B] == posX[A] + 1) return posY[D] < posY[C];
        if(posX[B] == posX[A] - 1) return posY[C] < posY[D];
        if(posY[B] == posY[A] + 1) return C < D;
        if(posY[B] == posY[A] - 1) return D < C;
        /*
           if (B == A + ::C) return (D - 1) % ::C < (C - 1) % ::C;
           if (B == A - ::C) return (C - 1) % ::C < (D - 1) % ::C;
           if (B == A + 1) return C < D;
           if (B == A - 1) return D < C;
           */
        std::cerr << A << ' ' << B << ' ' << C << ' ' << D << '\n';
        std::cerr << posX[A] << ' ' << posX[B] << '\n';
        abort();
    }

    void dfs(int i) {
        int j, x = e[i].u, y = e[i].v, z, bestV = 0, bestE = 0;
        //      fprintf(stderr, "search face #%d edge #%d (%d, %d)\n", F, i, x, y);
        belF[i] = F, face[F].eb(i);
        for (j = first[y]; j; j = next[j]) {
            if ((z = e[j].v) == x) continue;
            if (!bestV || judge(x, y, z, bestV)) bestV = z, bestE = j;
        }
        if (!bestE) {
            for (j = first[y]; j; j = next[j]) if (e[j].v == x) break;
            bestV = x, bestE = j;
        }
        if (belF[bestE] != F) dfs(bestE);
    }

    int main() {
        int i, f, h, t = 0; bool o;
        for (i = 1; i <= E; ++i)
            if (!belF[i]) ++F, dfs(i), remain[F] = face[F].size();
        for (i = 1; i <= F; ++i)
            for (int e : face[i])
                if (orient[e] && --remain[i] == 1) que[t++] = i;
        for (h = 0; h < t; ++h) {
            f = que[h], o = true;
            if (!remain[f]) continue;
            for (int e : face[f])
                if (orient[e]) o ^= orient[e] != e;
                else i = e;
            orient[ad(i)] = orient[i] = (o ? ad(i) : i);
            if (--remain[ f = belF[ad(i)] ] == 1) que[t++] = f;
        }
        for (i = 1; i <= E; ++i) assert(orient[i]);
        return 0;
    }
}

using std::cin;

int mp[100][100];
int main() {
    int i, j, v, n;
    cin >> R;
    C = R;
    V = 0;
    for(i = 1; i <= R; i++) {
        std::string s(C, '#');
        cin >> s;
        for(j = 1; j <= C; j++) {
            if(s[j-1] == '#') {
                mp[i][j] = ++V;
                posX[V] = i, posY[V] = j;
            }
        }
    }
    for (n = i = 1; i <= R; ++i, ++n)
        for (j = 1; j < C; ++j, ++n)
            if (mp[i][j] && mp[i][j+1])
                addedge(mp[i][j], mp[i][j+1]);
    for (n = i = 1; i < R; ++i)
        for (j = 1; j <= C; ++j, ++n)
            if (mp[i][j] && mp[i+1][j])
                addedge(mp[i][j], mp[i+1][j]);
    std::iota(p + 1, p + (V + 1), 1);
    for (i = 1; i <= E; i += 2)
        if (!join(e[i].u, e[i].v)) {
            orient[i] = orient[i + 1] = i;
            //          fprintf(stderr, "%d %d\n", e[i].u, e[i].v);
        }
    Planar::main();
    std::vector<std::tuple<int,int,int>> mat;
    for (i = 1; i <= E; ++i) if (orient[i] == i) {
        mat.eb(e[i].u-1, e[i].v-1, 1);
        mat.eb(e[i].v-1, e[i].u-1, -1);
    }
    std::cerr << "Matrix constructed success\n";
    std::cerr << V << ' ' << mat.size() << '\n';
    std::cout << V << ' ' << mat.size() << '\n';
    for(auto [a, b, c]: mat)
        std::cout << a << ' '<< b << ' ' << c << '\n';
    return 0;
}