最小全域木のコストを求める (daylight/graph/kruskal.hpp)

• View this file on GitHub
• Last update: 2024-12-26 20:32:55+09:00
• Include: #include "daylight/graph/kruskal.hpp"

Depends on

• 基本テンプレート (daylight/base.hpp)
• daylight/graph/base.hpp

Required by

• daylight/graph/all.hpp

Verified with

• test/aoj/grl/2_A.test.cpp

Code

#include "atcoder/all"
#include "daylight/base.hpp"
#include "daylight/graph/base.hpp"
using namespace atcoder;
/// @brief 最小全域木のコストを求める
/// @param V 頂点数
/// @param ES 辺集合
/// @return グラフが連結でなければLINF,連結ならば最小全域木のコスト
ll kruskal(int V, Edges<>& ES) {
	sort(ALL(ES), [](Edge<> const& a, Edge<> const& b) {
		if(a.cost != b.cost) return a.cost < b.cost;
		if(a.from != b.from) return a.from < b.from;
		return a.to < b.to;
	});
	ll ret = 0;
	dsu d(V);
	REP(i, SZ(ES)) {
		Edge e = ES[i];
		if(!d.same(e.from, e.to)) {
			ret += e.cost;
			d.merge(e.from, e.to);
		}
	}
	if(d.size(0) != V) {
		return LINF;
	}
	return ret;
}

Traceback (most recent call last):
  File "/home/runner/.local/lib/python3.10/site-packages/competitive_verifier/oj_resolve/resolver.py", line 181, in resolve
    bundled_code = language.bundle(path, basedir=basedir)
  File "/home/runner/.local/lib/python3.10/site-packages/competitive_verifier/oj/verify/languages/cplusplus.py", line 252, in bundle
    bundler.update(path)
  File "/home/runner/.local/lib/python3.10/site-packages/competitive_verifier/oj/verify/languages/cplusplus_bundle.py", line 482, in update
    self.update(
  File "/home/runner/.local/lib/python3.10/site-packages/competitive_verifier/oj/verify/languages/cplusplus_bundle.py", line 477, in update
    raise BundleErrorAt(
competitive_verifier.oj.verify.languages.cplusplus_bundle.BundleErrorAt: daylight/base.hpp: line 103: unable to process #include in #if / #ifdef / #ifndef other than include guards

Back to top page