verify/aizu/aizu-GRL_2_A.test.cpp

View this file on GitHub
Last update: 2023-01-08 14:16:34-05:00
Problem: https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_2_A

Depends on

Code

#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_2_A"

#include "../../library/contest/template-minimal.hpp"
#include "../../library/graphs/kruskal.hpp"

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n, m;
	cin >> n >> m;
	vector<array<int, 3>> edges;
	for (int i = 0; i < m; ++i) {
		int u, v, w;
		cin >> u >> v >> w;
		edges.push_back({w, u, v});
	}
	cout << kruskal(edges) << '\n';
	return 0;
}

#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_2_A"


#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <iostream>
#include <iomanip>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <vector>

using namespace std;


struct DSU {
  std::vector<int> e;

  DSU() = default;
  DSU(int n) { init(n); }

  void init(int n) { e = std::vector<int>(n, -1); }

  int get(int x) { return e[x] < 0 ? x : e[x] = get(e[x]); }

  bool same_set(int a, int b) { return get(a) == get(b); }

  int size(int x) { return -e[get(x)]; }

  bool unite(int x, int y) {
    x = get(x), y = get(y);
    if (x == y) return false;
    if (e[x] > e[y]) std::swap(x, y);
    e[x] += e[y];
    e[y] = x;
    return true;
  }
};

// weight, start, end

long long kruskal(std::vector<std::array<int, 3>> edge) {
	DSU D;
	int n = 0;
	for (auto& a : edge) {
		n = std::max(n, a[1]);
		n = std::max(n, a[2]);
	}
	++n;
	D.init(n);
	sort(edge.begin(), edge.end());
	long long ans = 0;
	for (auto& a : edge) {
		if (D.unite(a[1], a[2])) {
			ans += a[0];
		}
	}
	return ans;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n, m;
	cin >> n >> m;
	vector<array<int, 3>> edges;
	for (int i = 0; i < m; ++i) {
		int u, v, w;
		cin >> u >> v >> w;
		edges.push_back({w, u, v});
	}
	cout << kruskal(edges) << '\n';
	return 0;
}