Submission #66129528

---

Source Code Expand

#include <bits/stdc++.h>
#define ll long long

using namespace std;

typedef vector<ll> VD;
typedef vector<VD> VVD;
typedef vector<int> VI;

ll MinCostMatching(const VVD &cost, VI &Lmate, VI &Rmate) {
    int n = int(cost.size());

    // construct dual feasible solution
    VD u(n);
    VD v(n);
    for (int i = 0; i < n; i++) {
        u[i] = cost[i][0];
        for (int j = 1; j < n; j++) u[i] = min(u[i], cost[i][j]);
    }
    for (int j = 0; j < n; j++) {
        v[j] = cost[0][j] - u[0];
        for (int i = 1; i < n; i++) v[j] = min(v[j], cost[i][j] - u[i]);
    }

    // construct primal solution satisfying complementary slackness
    Lmate = VI(n, -1);
    Rmate = VI(n, -1);
    int mated = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (Rmate[j] != -1) continue;
            if (fabs(cost[i][j] - u[i] - v[j]) < 1e-10) {
                Lmate[i] = j;
                Rmate[j] = i;
                mated++;
                break;
            }
        }
    }

    VD dist(n);
    VI dad(n);
    VI seen(n);

    // repeat until primal solution is feasible
    while (mated < n) {
        // find an unmatched left node
        int s = 0;
        while (Lmate[s] != -1) s++;

        // initialize Dijkstra
        fill(dad.begin(), dad.end(), -1);
        fill(seen.begin(), seen.end(), 0);
        for (int k = 0; k < n; k++) dist[k] = cost[s][k] - u[s] - v[k];

        int j = 0;
        while (true) {
            // find closest
            j = -1;
            for (int k = 0; k < n; k++) {
                if (seen[k]) continue;
                if (j == -1 || dist[k] < dist[j]) j = k;
            }
            seen[j] = 1;

            // termination condition
            if (Rmate[j] == -1) break;

            // relax neighbors
            const int i = Rmate[j];
            for (int k = 0; k < n; k++) {
                if (seen[k]) continue;
                const ll new_dist = dist[j] + cost[i][k] - u[i] - v[k];
                if (dist[k] > new_dist) {
                    dist[k] = new_dist;
                    dad[k] = j;
                }
            }
        }

        // update dual variables
        for (int k = 0; k < n; k++) {
            if (k == j || !seen[k]) continue;
            const int i = Rmate[k];
            v[k] += dist[k] - dist[j];
            u[i] -= dist[k] - dist[j];
        }
        u[s] += dist[j];

        // augment along path
        while (dad[j] >= 0) {
            const int d = dad[j];
            Rmate[j] = Rmate[d];
            Lmate[Rmate[j]] = j;
            j = d;
        }
        Rmate[j] = s;
        Lmate[s] = j;

        mated++;
    }

    ll value = 0;
    for (int i = 0; i < n; i++) value += cost[i][Lmate[i]];

    return value;
}

const int dx[4] = { 0, 0, -1, 1 };
const int dy[4] = { -1, 1, 0, 0 };
int N, M;

inline int from(int x, int y) {
    return x * M + y;
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> N >> M;
    VVD A(N, VD(M, 0));
    ll sum = 0;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cin >> A[i][j];
            sum += A[i][j];
        }
    }
    const int ALL = N * M;
    VVD cost(ALL, VD(ALL, 0));
    VI Lmate(ALL), Rmate(ALL);
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            for (int dir = 0; dir < 4; dir++) {
                int nx = i + dx[dir];
                int ny = j + dy[dir];
                if (nx >= 0 && ny >= 0 && nx < N && ny < M) {
                    ll C = A[i][j] + A[nx][ny];
                    if (C < 0) {
                        cost[from(i, j)][from(nx, ny)] = C;
                        cost[from(nx, ny)][from(i, j)] = C;
                        Lmate[from(i, j)] = from(nx, ny);
                        Rmate[from(i, j)] = from(nx, ny);
                        Lmate[from(nx, ny)] = from(i, j);
                        Rmate[from(nx, ny)] = from(i, j);
                    }
                }
            }
        }
    }
    auto matching = MinCostMatching(cost, Lmate, Rmate);
    cout << sum - matching / 2 << endl;
}

Submission Info

Judge Result