제출 #7883

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
7883		gs14004	비용 (KOI11_cost)	C++98	24 / 24	60 ms	4216 KiB

cost

#include <cstdio>
#include <algorithm>
using namespace std;

struct edge{int s,e,x;}a[100005];
int cmp(edge a, edge b){return a.x > b.x;}

int p[100005],r[100005],sz[100005],n,m;
long long sum[100005];
void init(){
    for (int i=1; i<=n; i++) p[i] = i, sz[i] = 1;
}

int fnd(int x){
    if(p[x] == x) return x;
    else return p[x] = fnd(p[x]);
}

void uni(int x, int y){
    x = fnd(x);
    y = fnd(y);
    if(r[x] > r[y]) p[x] = y, sz[y] += sz[x];
    else p[y] = x, sz[x] += sz[y];
    if(r[x] == r[y]) r[y]++;
}

int main(){
    scanf("%d %d",&n,&m);
    for (int i=0; i<m; i++) {
        scanf("%d %d %d",&a[i].s,&a[i].e,&a[i].x);
    }
    sort(a,a+m,cmp);
    init();
    sum[0] = a[0].x;
    for (int i=1; i<=m; i++) {
        sum[i] = sum[i-1] + a[i].x;
    }
    long long res = 0;
    for (int i=0; i<m; i++) {
        if(fnd(a[i].s) == fnd(a[i].e)) continue;
        else{
            res += (sum[m] - (i?sum[i-1]:0))*sz[fnd(a[i].s)] * sz[fnd(a[i].e)];
            uni(a[i].s,a[i].e);
        }
        res %= 1000000000;
    }
    printf("%lld",res);
}

• Subtask 1: 4.8 / 4.8
• Subtask 2: 7.2 / 7.2
• Subtask 3: 12 / 12