Submission #2854007

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
using lint = long long int;
constexpr lint MOD = 1000000007;

lint power(lint x, lint n)
{
    lint ans = 1;
    while (n>0)
    {
        if (n & 1) (ans *= x) %= MOD;
        (x *= x) %= MOD;
        n >>= 1;
    }
    return ans;
}

struct UnionFind
{
    vector<int> par, rank;

    UnionFind(int N) {
        par = rank = vector<int>(N, 0);
        for (int i=0; i<N; i++) par[i] = i;
    }
    int find(int x) {
        if (par[x] == x) return x;
        else return par[x] = find(par[x]);
    }

    void unite(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) return;

        if (rank[x] < rank[y]) par[x] = y;
        else par[y] = x;
        if (rank[x] == rank[y]) rank[x]++;
    }

    bool same(int x, int y) {
        return find(x) == find(y);
    }
};

struct UndirectedGraph
{
    using Pint = pair<int, int>;
    int V;
    int E;
    vector<lint> weights;
    vector<vector<Pint>> to;
    vector<Pint> edges;
    UnionFind uf;

    UndirectedGraph(int V) : V(V), E(0),
                             to(vector<vector<Pint> >(V)),
                             uf(UnionFind(V)) {}

    void add_edge(int v1, int v2, lint w)
    {
        to[v1].push_back(Pint(v2, E));
        to[v2].push_back(Pint(v1, E));
        edges.push_back(Pint(v1, v2));
        weights.push_back(w);
        E++;
    }

    vector<int> edge_used;
    lint kruskal()
    {
        priority_queue<Pint, vector<Pint>, greater<Pint> > pq;
        for (int i=0; i<E; i++) pq.push(Pint(weights[i], i));

        lint ans = 0;
        while (!pq.empty())
        {
            Pint p = pq.top(); pq.pop();
            int v1 = edges[p.second].first;
            int v2 = edges[p.second].second;
            if (!uf.same(v1, v2))
            {
                uf.unite(v1, v2);
                ans += p.first;
                edge_used.push_back(p.second);
            }
        }
        return ans;
    }
};

int N, M;
lint X;

int main()
{
    cin >> N >> M >> X;
    UndirectedGraph graph(N);
    for (int i=0; i<M; i++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        graph.add_edge(u-1, v-1, w);
    }

    lint lowest = graph.kruskal();

    lint ans = 0;
    if (lowest == X) ans = (power(2, N-1) - 2 + MOD) * power(2, M-N+1) % MOD;

    vector<int> cand = graph.edge_used;
    sort(cand.begin(), cand.end());

    int ng_num = 0, good_num = 0;

    for (int i=0; i<M; i++)
    {
        if (binary_search(cand.begin(), cand.end(), i)) continue;
        graph.edge_used = {i};
        graph.uf = UnionFind(N);
        graph.uf.unite(graph.edges[i].first, graph.edges[i].second);
        lint w = graph.kruskal() + graph.weights[i];
        if (w < X) ng_num++;
        if (w == X) good_num++;
    }
    ans += (2LL * (power(2, good_num) - 1 + MOD) % MOD) * power(2, M-N+1-good_num-ng_num);
    ans %= MOD;
    cout << ans << endl;
}

Submission Info

Judge Result