結果
問題 |
No.3087 University Coloring
|
ユーザー |
👑 ![]() |
提出日時 | 2025-04-04 21:36:24 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 95 ms / 2,000 ms |
コード長 | 8,253 bytes |
コンパイル時間 | 949 ms |
コンパイル使用メモリ | 89,592 KB |
実行使用メモリ | 9,148 KB |
最終ジャッジ日時 | 2025-04-04 21:38:40 |
合計ジャッジ時間 | 5,016 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 33 |
ソースコード
#ifdef NACHIA #define _GLIBCXX_DEBUG #else #define NDEBUG #endif #include <iostream> #include <string> #include <vector> #include <algorithm> using i64 = long long; using u64 = unsigned long long; #define rep(i,n) for(i64 i=0; i<i64(n); i++) const i64 INF = 1001001001001001001; template<typename A> void chmin(A& l, const A& r){ if(r < l) l = r; } template<typename A> void chmax(A& l, const A& r){ if(l < r) l = r; } using namespace std; #include <utility> #include <cassert> namespace nachia{ template<class Elem> class CsrArray{ public: struct ListRange{ using iterator = typename std::vector<Elem>::iterator; iterator begi, endi; iterator begin() const { return begi; } iterator end() const { return endi; } int size() const { return (int)std::distance(begi, endi); } Elem& operator[](int i) const { return begi[i]; } }; struct ConstListRange{ using iterator = typename std::vector<Elem>::const_iterator; iterator begi, endi; iterator begin() const { return begi; } iterator end() const { return endi; } int size() const { return (int)std::distance(begi, endi); } const Elem& operator[](int i) const { return begi[i]; } }; private: int m_n; std::vector<Elem> m_list; std::vector<int> m_pos; public: CsrArray() : m_n(0), m_list(), m_pos() {} static CsrArray Construct(int n, std::vector<std::pair<int, Elem>> items){ CsrArray res; res.m_n = n; std::vector<int> buf(n+1, 0); for(auto& [u,v] : items){ ++buf[u]; } for(int i=1; i<=n; i++) buf[i] += buf[i-1]; res.m_list.resize(buf[n]); for(int i=(int)items.size()-1; i>=0; i--){ res.m_list[--buf[items[i].first]] = std::move(items[i].second); } res.m_pos = std::move(buf); return res; } static CsrArray FromRaw(std::vector<Elem> list, std::vector<int> pos){ CsrArray res; res.m_n = pos.size() - 1; res.m_list = std::move(list); res.m_pos = std::move(pos); return res; } ListRange operator[](int u) { return ListRange{ m_list.begin() + m_pos[u], m_list.begin() + m_pos[u+1] }; } ConstListRange operator[](int u) const { return ConstListRange{ m_list.begin() + m_pos[u], m_list.begin() + m_pos[u+1] }; } int size() const { return m_n; } int fullSize() const { return (int)m_list.size(); } }; } // namespace nachia namespace nachia{ struct Graph { public: struct Edge{ int from, to; void reverse(){ std::swap(from, to); } int xorval() const { return from ^ to; } }; Graph() : m_n(0), m_e(0), m_isUndir(false) {} explicit Graph(int n, bool undirected = false, int m = 0) : m_n(n), m_e(m), m_isUndir(undirected) {} explicit Graph(int n, const std::vector<std::pair<int, int>>& edges, int undirected = false) : m_n(n), m_isUndir(undirected){ m_e.resize(edges.size()); for(std::size_t i=0; i<edges.size(); i++) m_e[i] = { edges[i].first, edges[i].second }; } template<class Cin> static Graph Input(Cin& cin, int n, bool undirected, int m, int offset = 0){ Graph res(n, undirected, m); for(int i=0; i<m; i++){ int u, v; cin >> u >> v; res[i].from = u - offset; res[i].to = v - offset; } return res; } int numVertices() const noexcept { return m_n; } int numEdges() const noexcept { return int(m_e.size()); } int addNode() noexcept { return m_n++; } int addEdge(int from, int to){ m_e.push_back({ from, to }); return numEdges() - 1; } Edge& operator[](int ei) noexcept { return m_e[ei]; } const Edge& operator[](int ei) const noexcept { return m_e[ei]; } Edge& at(int ei) { return m_e.at(ei); } const Edge& at(int ei) const { return m_e.at(ei); } auto begin(){ return m_e.begin(); } auto end(){ return m_e.end(); } auto begin() const { return m_e.begin(); } auto end() const { return m_e.end(); } bool isUndirected() const noexcept { return m_isUndir; } void reverseEdges() noexcept { for(auto& e : m_e) e.reverse(); } void contract(int newV, const std::vector<int>& mapping){ assert(numVertices() == int(mapping.size())); for(int i=0; i<numVertices(); i++) assert(0 <= mapping[i] && mapping[i] < newV); for(auto& e : m_e){ e.from = mapping[e.from]; e.to = mapping[e.to]; } m_n = newV; } std::vector<Graph> induce(int num, const std::vector<int>& mapping) const { int n = numVertices(); assert(n == int(mapping.size())); for(int i=0; i<n; i++) assert(-1 <= mapping[i] && mapping[i] < num); std::vector<int> indexV(n), newV(num); for(int i=0; i<n; i++) if(mapping[i] >= 0) indexV[i] = newV[mapping[i]]++; std::vector<Graph> res; res.reserve(num); for(int i=0; i<num; i++) res.emplace_back(newV[i], isUndirected()); for(auto e : m_e) if(mapping[e.from] == mapping[e.to] && mapping[e.to] >= 0) res[mapping[e.to]].addEdge(indexV[e.from], indexV[e.to]); return res; } CsrArray<int> getEdgeIndexArray(bool undirected) const { std::vector<std::pair<int, int>> src; src.reserve(numEdges() * (undirected ? 2 : 1)); for(int i=0; i<numEdges(); i++){ auto e = operator[](i); src.emplace_back(e.from, i); if(undirected) src.emplace_back(e.to, i); } return CsrArray<int>::Construct(numVertices(), src); } CsrArray<int> getEdgeIndexArray() const { return getEdgeIndexArray(isUndirected()); } CsrArray<int> getAdjacencyArray(bool undirected) const { std::vector<std::pair<int, int>> src; src.reserve(numEdges() * (undirected ? 2 : 1)); for(auto e : m_e){ src.emplace_back(e.from, e.to); if(undirected) src.emplace_back(e.to, e.from); } return CsrArray<int>::Construct(numVertices(), src); } CsrArray<int> getAdjacencyArray() const { return getAdjacencyArray(isUndirected()); } private: int m_n; std::vector<Edge> m_e; bool m_isUndir; }; } // namespace nachia namespace nachia { struct DsuFast{ private: std::vector<int> w; public: DsuFast(int n = 0) : w(n, -1) {} int leader(int u){ if(w[u] < 0) return u; return w[u] = leader(w[u]); } int operator[](int u){ return leader(u); } int merge(int u, int v){ u = leader(u); v = leader(v); if(u == v) return u; if(-w[u] < -w[v]) std::swap(u, v); w[u] += w[v]; w[v] = u; return u; } int size(int u){ return -w[leader(u)]; } bool same(int u, int v){ return leader(u) == leader(v); } }; } // namespace nachia namespace nachia{ std::vector<int> MinimumSpanningForestKnownPriority( const nachia::Graph& graph, const std::vector<int>& edgePriorityOrdered = {} ){ int m = graph.numEdges(); auto dsu = nachia::DsuFast(graph.numVertices()); std::vector<int> ans; bool f = !edgePriorityOrdered.empty(); for(int i=0; i<m; i++){ int e = f ? edgePriorityOrdered[i] : i; int v = graph[e].from; int w = graph[e].to; if(dsu.same(v,w)) continue; ans.push_back(e); dsu.merge(v,w); } return ans; } template<class Weight> std::vector<int> MinimumSpanningForest( const nachia::Graph& graph, const std::vector<Weight>& weight ){ int m = graph.numEdges(); std::vector<int> P(m); for(int i=0; i<m; i++) P[i] = i; std::sort(P.begin(), P.end(), [&](int l, int r){ return weight[l] < weight[r]; }); return MinimumSpanningForestKnownPriority(graph, P); } } // namespace nachia void testcase(){ i64 N, M; cin >> N >> M; auto graph = nachia::Graph(N, true, M); vector<i64> W(M); rep(i,M){ cin >> graph[i].from >> graph[i].to >> W[i]; W[i] = -W[i]; } for(auto& [u,v] : graph){ u--; v--; } auto mst = nachia::MinimumSpanningForest(graph, W); i64 ans = 0; rep(i,mst.size()) ans -= W[mst[i]]; ans *= 2; cout << ans << "\n"; } int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); rep(t,1) testcase(); return 0; }