Codeforces 1095 F (贪心+ MST)

让标签带偏了。。所有点和最小的点连边，算上m个特殊边跑MST就行了。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<map>
#include<queue>
#include<vector>
#include<string>
#include<fstream>
using namespace std;
#define rep(i, a, n) for(int i = a; i <= n; ++ i);
#define per(i, a, n) for(int i = n; i >= a; -- i);
typedef long long ll;
const int N = 5e6 + 105;
const int mod = 1e9 + 7;
const double Pi = acos(- 1.0);
const ll INF = 1e18;
const int G = 3, Gi = 332748118;
ll qpow(ll a, ll b) { ll res = 1; while(b){ if(b & 1) res = (res * a) % mod; a = (a * a) % mod; b >>= 1;} return res; }
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
// bool cmp(int a, int b){return a > b;}
//


int n, m;
ll minn, a[N], res; 
int cnt = 0, pos = 0;
int root[N];
struct node{
    int x, y; ll z;
}e[N];

int Find(int x){
    return x == root[x] ? x : root[x] = Find(root[x]);
}

void Union(int x, int y){
    int tx = Find(x), ty = Find(y);
    if(tx != ty) root[ty] = tx; 
}

bool cmp(node a, node b){
    return a.z < b.z;
}

int main()
{
    scanf("%d%d",&n,&m);
    minn = INF;
    for(int i = 1; i <= n; ++ i) {
        scanf("%lld",&a[i]);
        if(a[i] < minn){
            minn = a[i]; pos = i;
        }
    }
    
    for(int i = 1; i <= n; ++ i){
        if(i == pos) continue;
        e[++ cnt] = (node){pos, i, a[i] + a[pos]};
    }
    for(int i = 1; i <= m; ++ i){
        int x, y; ll z; scanf("%d%d%lld",&x,&y,&z);
        e[++ cnt] = (node){x, y, z};
    }
    
    sort(e + 1, e + cnt + 1, cmp);
    for(int i = 0; i <= n; ++ i) root[i] = i;
    for(int i = 1; i <= cnt; ++ i){
        int tx = Find(e[i].x), ty = Find(e[i].y);
        if(tx == ty) continue;
        res += e[i].z; Union(e[i].x, e[i].y);
    }
    
    printf("%lld\n",res);
    return 0;
}
Codeforces 1095 F (贪心+ MST)

推荐阅读
