結果
問題 | No.1207 グラフX |
ユーザー |
|
提出日時 | 2020-08-30 15:24:33 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 641 ms / 2,000 ms |
コード長 | 4,045 bytes |
コンパイル時間 | 3,550 ms |
コンパイル使用メモリ | 208,708 KB |
最終ジャッジ日時 | 2025-01-13 22:38:59 |
ジャッジサーバーID (参考情報) |
judge3 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 46 |
ソースコード
#include"bits/stdc++.h"using namespace std;#define REP(k,m,n) for(int (k)=(m);(k)<(n);(k)++)#define rep(i,n) REP((i),0,(n))using ll = long long;using pii = pair<int, int>;using pll = pair<ll, ll>;using tp3 = tuple<ll, ll, ll>;using Mat = vector<vector<ll>>;constexpr int INF = 1 << 28;constexpr ll INFL = 1ll << 60;constexpr int dh[4] = { 0,1,0,-1 };constexpr int dw[4] = { -1,0,1,0 };bool isin(const int H, const int W, const int h, const int w) {return 0 <= h && h < H && 0 <= w && w < W;}class UnionFind {public:vector<int>rank, parent;//初期化UnionFind(int size) {rank.resize(size, 0);parent.resize(size, 0);rep(i, size)parent[i] = i;}//木の根を求めるint find(int x) {if (parent[x] == x)return x;else return parent[x] = find(parent[x]);}//xとyの属する集合を併合void unite(int x, int y) {x = find(x);y = find(y);if (x == y)return;if (rank[x] < rank[y])parent[x] = y;else {parent[y] = x;if (rank[x] == rank[y])rank[x]++;}}//xとyが同じ集合に属するか否かbool same(int x, int y) {return (find(x) == find(y));}};struct ModInt {static const ll MOD = 1000000007;// constructors etcModInt() :num(1ll) {}ModInt(ll num_) :num(num_%MOD) {}ModInt(const ModInt& modint) :num(modint.num%MOD) {}ll get()const { return num; }// operator etc// operator ll() const { return num; }// ll operator*() { return num; }ModInt& operator+=(const ModInt& r) { (num += r.num) %= MOD; return *this; }ModInt& operator-=(const ModInt& r) { (num += -r.num + MOD) %= MOD; return *this; }ModInt& operator*=(const ModInt& r) { (num *= r.num) %= MOD; return *this; }ModInt& operator/=(const ModInt& r) { (num *= r.inv().num) %= MOD; return *this; }ModInt pow(const ModInt& r)const {ll res = 1;ll x = num;ll n = r.num;while (n > 0) {if (n & 1)res = (res*x) % MOD;x = (x*x) % MOD;n >>= 1;}return res;}ModInt inv()const { return this->pow(MOD - 2); }ModInt operator+(const ModInt& r)const { return ModInt(*this) += r; }ModInt operator-(const ModInt& r)const { return ModInt(*this) -= r; }ModInt operator*(const ModInt& r)const { return ModInt(*this) *= r; }ModInt operator/(const ModInt& r)const { return ModInt(*this) /= r; }ModInt operator+(const ll& r)const { return *this + ModInt(r); }ModInt operator-(const ll& r)const { return *this - ModInt(r); }ModInt operator*(const ll& r)const { return *this * ModInt(r); }ModInt operator/(const ll& r)const { return *this / ModInt(r); }private:ll num;};ostream& operator<<(ostream& stream, const ModInt& val) { stream << val.get(); return stream; }// ============ template finished ============int dfs(const vector<vector<pll>>& edges, vector<ll>& childs, const int now, const int par) {childs[now] = 1;for (auto[nextIdx, _] : edges[now])if (nextIdx != par) {childs[now] += dfs(edges, childs, nextIdx, now);}return childs[now];}int main(){ll N, M, X;cin >> N >> M >> X;vector<vector<pll>> edges(N);vector<tp3> pairs;{UnionFind uf(N);rep(i, M) {ll x, y, z;cin >> x >> y >> z;x--; y--;if (uf.same(x, y))continue;uf.unite(x, y);edges[x].push_back({ y,z });edges[y].push_back({ x,z });pairs.push_back(make_tuple(x, y, z));}}vector<ll> childs(N, 0);dfs(edges, childs, 0, -1);ModInt res(0);for (auto[x, y, z] : pairs) {ll small = min(childs[x], childs[y]);auto way = ModInt(small) * (N - small);auto value = ModInt(X).pow(z);res += value * way;}cout << res << endl;return 0;}