#1198400 (C++23(gcc16)) No.3751 Nonopoly

• 問題: No.3751 Nonopoly
• ユーザー: C
• 提出日時: 2026-11-12 15:39:19
• 言語: C++23(gcc16) (gcc 16.2.0 + boost 1.92.0 + ACL)
• 結果: AC
• 実行時間: 48 ms / 2,000 ms
• コード長: 3,089 bytes
• コンパイル時間: 8,810 ms
• コンパイル使用メモリ: 422,488 KB
• 実行使用メモリ: 13,600 KB
• 最終ジャッジ日時: 2026-11-12 15:39:48
• 合計ジャッジ時間: 17,182 ms
• ジャッジサーバーID （参考情報）: judge4_0 / judge2_0

ファイルパターン	結果
sample	AC * 2
other	AC * 50

ソースコード

#if defined(__GNUC__) && !defined(__clang__)
#pragma GCC optimize("O3")
#if defined(__x86_64__) || defined(__i386__)
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#endif
#endif
#include <bits/stdc++.h>
#include <atcoder/all>
#define each(x, v) for (auto&& x : v)
#define each2(x, y, v) for (auto&& [x, y] : v)
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define all(x) begin(x),end(x)
#define sz(x) (int)(x).size()
using namespace std;
using namespace atcoder;
using ll=long long;
using ull=unsigned long long;
using ld=long double;
using vll=vector<ll>;
using vvll=vector<vll>;
using vi=vector<int>;
using vvi=vector<vi>;
using pll=pair<ll,ll>;
using pi=pair<int,int>;

// using mint=modint998244353;
using mint=modint1000000007;
// using mint2=static_modint<2>;

// using mint=LazyMontgomeryModInt<998244353>;
using vm=vector<mint>;
using vvm=vector<vm>;

#line 2 "graph/static-graph.hpp"

namespace StaticGraphImpl {

template <typename T, bool Cond = is_void<T>::value>
struct E;
template <typename T>
struct E<T, false> {
  int to;
  T cost;
  E() {}
  E(const int& v, const T& c) : to(v), cost(c) {}
  operator int() const { return to; }
};
template <typename T>
struct E<T, true> {
  int to;
  E() {}
  E(const int& v) : to(v) {}
  operator int() const { return to; }
};

template <typename T = void>
struct StaticGraph {
 private:
  template <typename It>
  struct Es {
    It b, e;
    It begin() const { return b; }
    It end() const { return e; }
    int size() const { return int(e - b); }
    auto&& operator[](int i) const { return b[i]; }
  };
  
  int N, M, ec;
  vector<int> head;
  vector<pair<int, E<T>>> buf;
  vector<E<T>> es;

  void build() {
    partial_sum(begin(head), end(head), begin(head));
    es.resize(M);
    for (auto&& [u, e] : buf) es[--head[u]] = e;
  }

 public:
  StaticGraph(int _n, int _m) : N(_n), M(_m), ec(0), head(N + 1, 0) {
    buf.reserve(M);
  }

  template <typename... Args>
  void add_edge(int u, Args&&... args) {
#pragma GCC diagnostic ignored "-Wnarrowing"
    buf.emplace_back(u, E<T>{std::forward<Args>(args)...});
#pragma GCC diagnostic warning "-Wnarrowing"
    ++head[u];
    if ((int)buf.size() == M) build();
  }

  Es<typename vector<E<T>>::iterator> operator[](int u) {
    return {begin(es) + head[u], begin(es) + head[u + 1]};
  }
  const Es<typename vector<E<T>>::const_iterator> operator[](int u) const {
    return {begin(es) + head[u], begin(es) + head[u + 1]};
  }
  int size() const { return N; }
};

}  // namespace StaticGraphImpl

using StaticGraphImpl::StaticGraph;

/**
 * @brief Static Graph
 * @docs docs/graph/static-graph.md
 */

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
	int N,M;
	cin>>N>>M;
	if(M==0){
		cout<<M<<'\n';
		return 0;
	}
	StaticGraph<int>g(N,2*M);
	rep(i,0,M){
		int u,v,w;
		cin>>u>>v>>w;
		--u,--v;
		g.add_edge(u,v,w);
		g.add_edge(v,u,w);
	}
	vll D(N);
	rep(u,0,N){
		each2(v,w,g[u])D[u]+=w;
	}
	sort(all(D),greater<ll>());
	ll ans=0;
	rep(i,0,N){
		if(i&1)ans-=D[i];
		else ans+=D[i];
	}
	cout<<ans/2<<'\n';
}