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.     vector<int> dp(1 << m);
  65.     for (int msk = (1 << m) - 1; msk >= 0; msk--) {
  66.         DSU d(n);
  67.         bool can = true;
  68.         for (int i = 0; i < m; i++) {
  69.             if (msk >> i & 1) {
  70.                 if (!d.merge(edges[i][0], edges[i][1])) {
  71.                     can = false;
  72.                     break;
  73.                 }
  74.             }
  75.         }
  76.         if (!can)
  77.         continue;
  78.  
  79.         vector<array<int, 2>> cur;
  80.         int cnt = 0;
  81.         for (int i = 0; i < m; i++) {
  82.             if (msk >> i & 1) {
  83.                 continue;
  84.             }
  85.             if (d.find_root(edges[i][0]) == d.find_root(edges[i][1]))
  86.                 continue;
  87.             cur.push_back({edges[i][2], i});
  88.             cnt++;
  89.         }
  90.  
  91.         for (auto [v, i] : cur) {
  92.             dp[msk] += ((dp[msk | (1 << i)] + v) % MOD) * inv(cnt) % MOD;
  93.             dp[msk] %= MOD;
  94.         }
  95.     }
  96.     cout << dp[0];
  97. }
  98.  
  99.  
  100. signed main() {
  101.     ios_base::sync_with_stdio(false); 
  102.     cin.tie(NULL); cout.tie(NULL);
  103.     // #ifndef ONLINE_JUDGE 
  104.     //    freopen("input.txt", "r", stdin); 
  105.     //    freopen("output.txt", "w", stdout); 
  106.     // #endif 
  107.     int t; t = 1;
  108.     //  cin >> t;
  109.     while (t--) solve();
  110.     return 0;
  111. }
Success #stdin #stdout 0s 5316KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/t2iDHB
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!