제출 #16248

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
16248		eaststar	비용 (KOI11_cost)	C++14	24 / 24	64 ms	3036 KiB

cost

#include <cstdio>
#include <algorithm>
struct data{
    int x,y,w;
    bool operator<(const data&r)const{
        return w>r.w;
    }
}path[100010];
int g[100010],cnt[100010],n;
long long int ans,w;
int seek(int nod){
    if(g[nod]==nod)return nod;
    return g[nod]=seek(g[nod]);
}
void merge(int a,int b){
    a=seek(a);
    b=seek(b);
    if(a==b)
    {
        ++n;
        return;
    }
    ans+=w*cnt[a]*cnt[b];
    g[b]=a;
    cnt[a]+=cnt[b];
}
int main(){
    int i,m,t;
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;++i){
        scanf("%d%d%d",&path[i].x,&path[i].y,&path[i].w);
        w+=path[i].w;
    }
    std::sort(&path[1],&path[m+1]);
    for(i=1;i<=n;++i)g[i]=i,cnt[i]=1;
    for(i=1;i<n&&i<=m;++i){
        merge(path[i].x,path[i].y);
        w-=path[i].w;
        ans%=1000000000;
    }
    printf("%d",ans);
    return 0;
}

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