Submission #3006858

---

Source Code Expand

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include <string>
#include <set>
#include <map>
#define REP(i,n) for(ll i = 0; i < (ll)n; i++)
#define INF 1000000000000000
using namespace std;
typedef long long ll;
typedef double db;
typedef string str;

struct UnionFind{
  vector<ll> par;
  vector<ll> rank;
  vector<ll> sizes;

  UnionFind(ll n){
    init(n);
  }

  void init(ll n){
    par.resize(n);
    rank.resize(n);
    sizes.resize(n);
    REP(i,n){
      par[i] = i;
      rank[i] = 0;
      sizes[i] = 1;
    }
  }

  ll find(ll x){
    if(par[x] == x){
      return x;
    }else{
      return par[x] = find(par[x]);
    }
  }

  void unite(ll x, ll y){
    x = find(x);
    y = find(y);
    if(x==y) return;
    if(rank[x]<rank[y]){
      par[x] = y;
      sizes[y] += sizes[x];
    }else{
      par[y] = x;
      sizes[x] += sizes[y];
      if(rank[x]==rank[y]) rank[x]++;
    }
  }

  bool same(ll x, ll y){
    return find(x)==find(y);
  }

  ll size(ll x){
    return sizes[find(x)];
  }
};
struct edge{ll from, to, cost;};
bool compare_edge(const edge& e1, const edge& e2){
  return e1.cost<e2.cost;
}
struct graph{
  vector<edge> es;
  ll V;
  graph(ll n){
    init(n);
  }
  void init(ll n){
    V = n;
  }
  void add_edge(ll from, ll to, ll cost){
    edge e;
    e.from = from, e.to = to, e.cost = cost;
    es.push_back(e);
  }
  ll kruskal(){
    sort(es.begin(),es.end(),compare_edge);
    UnionFind uf(V);
    ll res = 0;
    for(auto e : es){
      if(!uf.same(e.from,e.to)){
        uf.unite(e.from,e.to);
        res += e.cost;
      }
    }
    return res;
  }
};

ll h,w;
ll calc_pos(ll y, ll x){
  return y*w+x;
}

int main(){
  cin >> h >> w;
  ll sx, sy, gx, gy;
  cin >> sx >> sy >> gx >> gy;
  graph g(h*w);
  ll p[h][w];
  ll point_sum = 0;
  REP(i,h)REP(j,w){
    cin >> p[i][j];
    point_sum += p[i][j];
  }
  REP(i,h-1)REP(j,w){
    g.add_edge(calc_pos(i,j),calc_pos(i+1,j),-p[i][j]*p[i+1][j]);
  }
  REP(i,h)REP(j,w-1){
    g.add_edge(calc_pos(i,j),calc_pos(i,j+1),-p[i][j]*p[i][j+1]);
  }
  ll max_bonus = -g.kruskal();
  cout << point_sum + max_bonus << endl;
  return 0;
}

Submission Info

Judge Result