Submission #3176456

---

Source Code Expand

#include<bits/stdc++.h>
#pragma warning(disable:4996)
using namespace std;
using ll = long long;
const int dx[4] = { 1,0,-1,0 }, dy[4] = { 0,1,0,-1 };
//#define int long long
int H, W, sx, sy, gx, gy;
vector < vector<int>>grid;
class union_find_tree {
private:
	vector<int>par, rank_;
public:
	union_find_tree(int n) :par(n), rank_(n) {
		for (int i = 0; i < n; i++) {
			par[i] = i;
			rank_[i] = 0;
		}
	}

	void unite(int x, int y) {
		x = root(x);
		y = root(y);
		if (x == y) {
			return;
		}
		if (rank_[x] < rank_[y]) {
			par[x] = y;
		}
		else if (rank_[x] == rank_[y]) {
			par[y] = x;
			rank_[x]++;

		}
		else if (rank_[y] < rank_[x]) {
			par[y] = x;
		}
	}
	int root(int x) {
		if (par[x] == x) {
			return x;
		}
		return par[x] = root(par[x]);
	}
	bool same(int x, int y) {
		return root(x) == root(y);
	}
};

struct edge {
	int from, to, cost;
	bool operator<(const edge& other)const {
		//return cost < other.cost;
		return other.cost < cost;
	}
};

using edges = vector<edge>;

int kruskal(union_find_tree& uf, edges&  es, int V) {


	sort(es.begin(), es.end());
	int E = es.size();

	int res = 0;
	for (int i = 0; i < E; i++) {
		if (!uf.same(es[i].from, es[i].to)) {
			uf.unite(es[i].from, es[i].to);
			res += es[i].cost;
		}
	}
	return res;
}
signed main(){
	cin >> H >> W >> sx >> sy >> gx >> gy;
	grid.resize(H);
	int sum = 0;
	for (int i = 0; i < H; i++) {
		for (int j = 0; j < W; j++) {
			int p;
			cin >> p;
			sum += p;
			grid[i].push_back(p);
		}
	}
	vector<edge>es;
	union_find_tree uf(H*W);
	for (int i = 0; i < H; i++) {
		for (int j = 0; j < W - 1; j++) {
			edge e;
			e.cost = grid[i][j] * grid[i][j + 1];
			e.from = i * W + j;
			e.to = i * W + j + 1;
			es.push_back(e);
			edge e1;
			e1.cost= grid[i][j] * grid[i][j + 1];
			e1.from = i * W + j+1;
			e1.to = i * W + j;
			es.push_back(e1);
		}
	}
	for (int i = 0; i < W; i++) {
		for (int j = 0; j < H - 1; j++) {
			edge e;
			e.cost = grid[i][j] * grid[i+1][j];
			e.from = i * W + j;
			e.to = (i+1) * W + j;
			es.push_back(e);
			edge e1;
			e1.cost = grid[i+1][j] * grid[i][j];
			e1.from = i * W + j;
			e1.to = (i+1) * W + j;
			es.push_back(e1);
		}
	}
	int res = kruskal(uf, es, H*W);
	cout << res + sum << endl;
}

Submission Info

Judge Result