最小全域木(ABC 065 D問題)

めっちゃ難しかった
問題
以下ネタバレ注意

1. struct edge { int u, v, cost; };
2. struct vertex { int p, x, y; };
3.  
4. //比較関数
5. bool comp(const edge& e1, const edge&e2) {
6. return e1.cost < e2.cost;
7. }
8. bool compX(const vertex& v1, const vertex& v2) {
9. return v1.x < v2.x;
10. }
11. bool compY(const vertex& v1, const vertex& v2) {
12. return v1.y < v2.y;
13. }
14.  
15. edge es[2 * MAX];
16. vertex ver[MAX];
17. int N; int E;
18.  
19. ll kruskal() {
20. sort(es, es + E, comp);//costでソート
21. init(N);
22. ll res = 0;
23. //コストが小さい辺から順に追加する
24. REP(i, E) {
25. edge e = es[i];
26. //もし閉路ができなければその辺を追加する
27. if (!same(e.u, e.v)) {
28. unite(e.u, e.v);
29. res += e.cost;
30. }
31. }
32. return res;
33. }
34.  
35. int main() {
36. cin >> N;
37. REP(i, N) {
38. int x, y;
39. cin >> x >> y;
40. ver[i] = {i, x,y };
41. }
42. E = 2*(N-1);
43. //x座標でソート
44. sort(ver, ver + N, compX);
45. REP(i, N - 1) {
46. //隣接した点の間にコスト|x1-x2|の辺を貼る
47. es[i] = { ver[i].p,ver[i + 1].p,abs(ver[i].x - ver[i + 1].x) };
48. }
49. //y座標でソート
50. sort(ver, ver + N, compY);
51. REP(i, N - 1) {
52. es[N - 1 + i] = { ver[i].p,ver[i + 1].p,abs(ver[i].y - ver[i + 1].y) };
53. }
54. ll ans=kruskal();
55. cout << ans << endl;
56. }