Submission #2245237

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using pii = pair<int, int>;

template <class T>
struct Kruskal {
  struct UnionFind {
    int N;
    vector<int> sz_tree, parent;
    UnionFind() {}
    UnionFind(int N) : N(N), sz_tree(N, 1), parent(N) {
      iota(parent.begin(), parent.end(), 0);
    }
    int root(int x) {
      return parent[x] == x ? x : parent[x] = root(parent[x]);
    }
    void merge(int x, int y) {
      if ((x = root(x)) == (y = root(y))) return;
      if (sz_tree[x] < sz_tree[y]) swap(x, y);
      sz_tree[x] += sz_tree[y];
      parent[y] = x;
    }
    bool same(int x, int y) {
      return root(x) == root(y);
    }
    int size(int x) {
      return sz_tree[root(x)];
    }
  };
  struct edge {
    int from, to; T cost;
    edge() {}
    edge(int f, int t, T c) : from(f), to(t), cost(c) {}
  };
 
  int N;
  vector<edge> es;
  Kruskal() {}
  Kruskal(int N) : N(N) {}
 
  void add_edge(int from, int to, T cost) {
    es.emplace_back(from, to, cost);
  }
  T mst() {
    T res = 0;
    UnionFind uf(N);
    sort(es.begin(), es.end(), [&](edge a, edge b) {
      return a.cost < b.cost;
    });
    for (auto &e : es) {
      if (uf.same(e.from, e.to)) continue;
      uf.merge(e.from, e.to);
      res += e.cost;
    }
    return res;
  }
};

int dy[] = {-1, 0, 0, 1};
int dx[] = {0, -1, 1, 0};

int main() {
  cin.tie(0);
  ios_base::sync_with_stdio(false);
  cout << fixed << setprecision(10);
  
  int H, W;
  cin >> H >> W;

  pii S, G;
  cin >> S.first >> S.second;
  cin >> G.first >> G.second;
  S.first--, S.second--;
  G.first--, G.second--;

  int P[110][110];
  int sum = 0;
  for (int i = 0; i < H; i++) {
    for (int j = 0; j < W; j++) {
      cin >> P[i][j];
      sum += P[i][j];
    }
  }

  Kruskal<int> K(H * W);
  for (int i = 0; i < H; i++) {
    for (int j = 0; j < W; j++) {
      for (int k = 0; k < 4; k++) {
        int ni = i + dy[k], nj = j + dx[k];
        if (ni >= 0 && ni < H && nj >= 0 && nj < W) {
          K.add_edge(i * W + j, ni * W + nj, -P[i][j] * P[ni][nj]);
          K.add_edge(ni * W + nj, i * W + j, -P[i][j] * P[ni][nj]);
        }
      }
    }
  }
  cout << sum - K.mst() << endl;

  return 0;
}

Submission Info

Judge Result