Submission #4018623

---

Source Code Expand

#include<iostream>
#include<cmath>
#include<cstdlib>
#include<string>
#include<cstring>
#include<algorithm>
#include<vector>

using namespace std;

const int MAX_N = 1e4 + 1;
int H, W;
int P[101][101];
bool used[MAX_N];
int par[MAX_N];
int UFTrank[MAX_N];
int Sx, Sy, Gx, Gy;
void init(int n) {
   for (int i = 0; i < n; i++) {
      par[i] = i;
      UFTrank[i] = 0;
   }
}

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

void unite(int x, int y) {
   x = find(x);
   y = find(y);
   if (x == y) return;

   if (UFTrank[x] < UFTrank[y]) {
      par[x] = y;
   } else {
      par[y] = x;
      if (UFTrank[x] == UFTrank[y]) UFTrank[x]++;
   }
}

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

struct edge { int u, v, cost; };

bool comp(const edge& e1, const edge& e2) {
   return e1.cost > e2.cost;
}

edge es[MAX_N * 2];

int main() {
   cin >> H >> W;
   int V = H * W;
   cin >> Sx >> Sy;
   cin >> Gx >> Gy;
   int sum = 0;
   for (int h = 0; h < H; h++) {
      for (int w = 0; w < W; w++) {
         cin >> P[h][w];
         sum += P[h][w];
      }
   }

   int E = 0;
   for (int h = 0; h < H; h++) {
      for (int w = 0; w < W - 1; w++) {
         es[E].u = h * W + w;
         es[E].v = h * W + w + 1;
         es[E].cost = P[h][w] * P[h][w + 1];
         E++;
      }
   }
   for (int h = 0; h < H - 1; h++) {
      for (int w = 0; w < W; w++) {
         es[E].u = h * W + w;
         es[E].v = (h + 1) * W + w;
         es[E].cost = P[h][w] * P[h + 1][w];
         E++;
      }
   }
   
   sort(es, es + E, comp);
   init(V);
   int ans = 0;
   memset(used, false, sizeof(used));
   for (int i = 0; i < E; i++) {
      edge e = es[i];
      // cout << i << " " << e.u << " " << e.v << " " << e.cost << endl;
      if (!same(e.u, e.v)) {
         unite(e.u, e.v);
         ans += e.cost;
      }
   }
   ans += sum;
   cout << ans << endl;
   return 0;
}

Submission Info

Judge Result