ARC093 E - Bichrome Spanning Tree

ARC093_E.cpp

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define all(v) (v).begin(), (v).end()
#define resz(v, ...) (v).clear(), (v).resize(__VA_ARGS__)
#define reps(i, m, n) for(int i = (int)(m); i < (int)(n); i++)
#define rep(i, n) reps(i, 0, n)

template<class T1, class T2> void chmin(T1 &a, T2 b){if(a>b)a=b;}
template<class T1, class T2> void chmax(T1 &a, T2 b){if(a<b)a=b;}

using Pi = pair<int, int>;
using Tapris = tuple<int, int, int>;
using vint = vector<int>;

const int inf = 1LL << 55;
const int mod = 1e9 + 7;

struct UnionFind {
  vector<int> data;
  UnionFind(int n):data(n, -1){}
  int find(int x) {
    if(data[x] < 0) return x;
    return data[x] = find(data[x]);
  }
  int size(int x) {
    return -data[find(x)];
  }
  bool same(int x, int y) {
    return find(x) == find(y);
  }
  void unite(int x, int y) {
    x = find(x), y = find(y);
    if(x == y) return;
    if(data[x] > data[y]) swap(x, y);
    data[x] += data[y];
    data[y] = x;
  }
};

signed main() {
  cin.tie(0);
  ios_base::sync_with_stdio(0);
  cout << fixed << setprecision(12);

  struct edge {
    int u, v, w;
    edge(){}
    edge(int u, int v, int w):u(u), v(v), w(w){}
    bool operator < (const edge& e) const {
      return w < e.w;
    }
  };

  int n, m, x;
  cin >> n >> m >> x;
  vector<edge> es;
  rep(i, m) {
    int u, v, w;
    cin >> u >> v >> w;
    --u, --v;
    es.emplace_back(u, v, w);
  }
  sort(all(es));

  int cnt = 0;
  int cnt_no = 0;
  rep(i, m) {
    UnionFind uf(n);
    int sum = es[i].w;
    uf.unite(es[i].u, es[i].v);
    rep(j, m) {
      edge e = es[j];
      if(!uf.same(e.u, e.v)) {
	uf.unite(e.u, e.v);
	sum += e.w;
      }
    }
    if(sum == x) ++cnt;
    else if(sum < x) ++cnt_no;
  }

  vint pow2(m+1);
  pow2[0] = 1;
  rep(i, m) pow2[i+1] = pow2[i]*2%mod;

  int ans = 0;
  if(cnt == 0) ans = 0;
  else if(cnt_no == 0) ans = (pow2[cnt]+mod-2)%mod*pow2[m-cnt-cnt_no]%mod;
  else ans =(pow2[cnt]+mod-1)%mod*pow2[m-cnt-cnt_no]%mod*2%mod;

  cout << ans << endl;

  return 0;
}