Created
March 29, 2018 04:50
-
-
Save takageymt/ce60892f7405df79920b2604f963d852 to your computer and use it in GitHub Desktop.
ARC093 E - Bichrome Spanning Tree
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment