bzoj1232 [Usaco2008Nov]安慰奶牛cheer

传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=1232

【题解】

这种删边的题一般都是最小生成树，考虑边权，因为要往返，所以边权是原来边权*2+两端点权。

这样起点会少算一次。我们求出最小生成树后找一个点权最小的当起点就行了。。

# include <stdio.h>
# include <string.h>
# include <iostream>
# include <algorithm>
// # include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
const int M = 5e5 + 10;
const int mod = 1e9+7;

# define RG register
# define ST static

int n, m, w[M], id[M], D;

struct pa {
    int u, v, w;
    pa() {}
    pa(int u, int v, int w) : u(u), v(v), w(w) {}
    friend bool operator < (pa a, pa b) {
        return a.w<b.w;
    }
}e[M];

int fa[M];
inline int getf(int x) {
    return fa[x] == x ? x : fa[x] = getf(fa[x]);
}

int main() {
    cin >> n >> m; D = m-n+1;
    for (int i=1; i<=n; ++i) fa[i] = i, scanf("%d", w+i);
    for (int i=1, u, v, _w; i<=m; ++i) {
        scanf("%d%d%d", &u, &v, &_w);
        e[i] = pa(u, v, 2*_w + w[u] + w[v]);
    }
    sort(e+1, e+m+1);
    ll ans = 0;
    int cnt = 0;
    for (int i=1; i<=m; ++i) {
        int fu = getf(e[i].u), fv = getf(e[i].v);
        if(fu == fv) continue;
        fa[fu] = fv;
        ans += e[i].w;
        ++cnt;
        if(cnt == n-1) break;
    }
    int mi = 1e9;
    for (int i=1; i<=n; ++i) mi = min(mi, w[i]);
    ans += mi;
    cout << ans;
    return 0;
}