fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define endl     '\n'
  5. #define int      long long
  6.  
  7. const int N = 2e5, oo = 2e18, MOD = 1e9+7;
  8.  
  9. struct DSU {
  10.   vector<int> sizes;
  11.   vector<int> parent;
  12.   DSU(int n) {
  13.     sizes.resize(n + 1);
  14.     parent.resize(n + 1);
  15.     for (int i = 0; i <= n; i++) {
  16.       parent[i] = i;
  17.       sizes[i] = 1;
  18.     }
  19.   }
  20.   int find_root(int u) {
  21.     if (parent[u] == u)
  22.       return u;
  23.  
  24.     return parent[u] = find_root(parent[u]);
  25.   }
  26.   bool merge(int u, int v) {
  27.     int root_u = find_root(u);
  28.     int root_v = find_root(v);
  29.     if (root_u == root_v)
  30.       return 0;
  31.  
  32.     if (sizes[root_u] > sizes[root_v])
  33.       swap(root_u, root_v);
  34.  
  35.     parent[root_u] = root_v;
  36.     sizes[root_v] += sizes[root_u];
  37.     return 1;
  38.   }
  39. };
  40.  
  41. int powmod(int b, int p) {
  42.     int res = 1;
  43.     while (p) {
  44.         if (p & 1) res = (res * b) % MOD;
  45.         b = (b * b) % MOD;
  46.         p >>= 1;
  47.     }
  48.     return res;
  49. }
  50.  
  51. int inv(int b) {
  52.     return powmod(b, MOD - 2);
  53. }
  54.  
  55.  
  56. void solve() {
  57.     int n, m; cin >> n >> m;
  58.     vector<array<int, 3>> edges(m);
  59.     for (int i = 0; i < m; i++) {
  60.         for (int j = 0; j < 3; j++) cin >> edges[i][j];
  61.         edges[i][0]--;
  62.         edges[i][1]--;
  63.     }
  64.     int ans = 0, cnt = 0;
  65.     for (int msk = 0; msk < (1 << m); msk++) {
  66.         if (__builtin_popcount(msk) != (n-1)) 
  67.             continue;
  68.         DSU d(n);
  69.         bool can = true;
  70.         int val = 0;
  71.         for (int i = 0; i < m; i++) {
  72.             if (msk >> i & 1) {
  73.                 if (!d.merge(edges[i][0], edges[i][1])) {
  74.                     can = false;
  75.                     break;
  76.                 }
  77.                 val += edges[i][2];
  78.             }
  79.         }
  80.         if (!can)
  81.             continue;   
  82.         cnt++;
  83.         ans = (ans + val) % MOD;
  84.     }
  85.     ans = (ans * inv(cnt)) % MOD;
  86.     cout << ans;
  87. }
  88.  
  89.  
  90. signed main() {
  91.     ios_base::sync_with_stdio(false); 
  92.     cin.tie(NULL); cout.tie(NULL);
  93.     // #ifndef ONLINE_JUDGE 
  94.     //    freopen("input.txt", "r", stdin); 
  95.     //    freopen("output.txt", "w", stdout); 
  96.     // #endif 
  97.     int t; t = 1;
  98.     //  cin >> t;
  99.     while (t--) solve();
  100.     return 0;
  101. }
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/J5fjhQ
language:
C++ (gcc 8.3)
created:
5 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!