Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
ARC093 E - Bichrome Spanning Tree
#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
You can’t perform that action at this time.