水渠设计

问题描述

你现在是城市的主人
现在有 $n$ 个田地需要灌溉。
可以选择修建 $m$ 个引水渠，第 $i$ 条从第 $a$ 个田地到第 $b$ 个田地，花费 $c$ 元。
现在可以买任意多个抽水机，买一个抽水机需要花费 $p$ 元。如果在一个田地旁边安置一个抽水机，则该田地会被灌溉。
水可以顺着水渠流动。
求让每一块田地都能被灌溉的最小花费。

输入格式

第一行三个整数 $n,m,p$ , $0\le n,m\le10^5,p\le 10^9$
接下来有 $m$ 行，每行 $a,b,c$ 代表修建了一条从第 $a$ 个田地，到第 $b$ 个田地的水渠，花费 $c$ 元。
$1\le a,b\le n$，$c<=10^9$

输出格式

输出一个数表示答案。

样例输入

5 5 2
1 2 1
2 3 3
3 4 5
1 3 2
1 4 1

样例输出

8

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MAXN 100002
struct edge {
    ll u, v, next, w;
    bool operator<(const edge& e) {
        return w < e.w;
    }
} e[3 * MAXN];

ll tot = 0;
vector<ll> head(MAXN, -1);

void addEdge(const ll& u, const ll& v, const ll& w) {
    e[tot].u = u, e[tot].v = v, e[tot].w = w, e[tot].next = head[u], head[u] = tot++;
}

/*void add2Edge(const ll& u, const ll& v, const ll& w) {
    addEdge(u, v, w), addEdge(v, u, w);
}*/

ll par[MAXN];

void init(ll n) {
    for (ll i = 0; i <= n; ++i)
        par[i] = i;
}

ll find(ll x) {
    return par[x] == x ? x : par[x] = find(par[x]);
}

/*bool same(ll x, ll y) {
    return find(x) == find(y);
}*/

bool unite(ll x, ll y) {
    x = find(x), y = find(y);
    if (x == y)
        return false;
    par[x] = y;
    return true;
}
/*bool cmp(const edge& e1, const edge& e2) {
    return e1.w < e2.w;
}*/

ll n, m, p, a, b, c;

ll kruskal() {
    // sort(e, e + tot, cmp);
    sort(e, e + tot);
    init(n);
    ll ans = 0, cnt = 0;
    for (ll i = 0; i < tot; ++i) {
        edge& e0 = e[i];
        if (unite(e0.u, e0.v)) {
            ans += e0.w;
            if (++cnt == n)  // 剪枝
                return ans;
        }
    }
    return -1;
}

int main() {
    scanf("%lld%lld%lld", &n, &m, &p);
    for (ll i = 1; i <= n; ++i)  // 加入超级源点
        addEdge(0, i, p);
    for (ll i = 1; i <= m; ++i) {
        scanf("%lld%lld%lld", &a, &b, &c);
        addEdge(a, b, c);
    }
    cout << kruskal();  // 最小生成树
    return 0;
}