BOJ 2463 - 비용

문제 링크 : https://www.acmicpc.net/problem/2463

문제 소개

그래프가 주어진다. 이 문제에서 Cost(u,v)는 가장 적은 비용의 간선부터 차례대로 끊어나갈 때, 점 u와 점 v가 처음으로 다른 컴포넌트가 될 때 까지 끊은 간선의 가중치의 총합이다. 이때 주어진 그래프에서 임의의 i<j인 (i,j)쌍에 대해 Cost(i,j)의 합을 출력하는 것이 목표이다.

문제 풀이

 이것은 굉장히 중요한 부분이다. 무엇인가를 분리하거나 끊는 문제가 나오게 되면 그 문제가 오프라인인지부터 확인해라. 여기서 오프라인이라함은 그 요구하는 것들이 여러개가 있을 때 그 처리 순서를 바꿔도 아무런 문제가 없는 것을 보통 의미한다. 일단 우리는 분리하는 것보다 합치는 것이 편하다. 특히 union & find 를 이용하면 굉장히 빠르게 컴퍼넌트들을 합칠 수 있다. 또한 오프라인이라는 점을 이용하면 거꾸로 문제를 해결해도 상관이 없다. 조건의 반대로 간선을 추가해가면서 합치는 기법이고, 생각보다 몇몇문제에 유용하게 쓰일 테크닉이다.

 가장 가중치가 큰 간선부터 그래프에 추가해주자. 이때 어떤 두 점 i와 j가 처음으로 연결이 되었다면 Cost(i,j)는 마지막으로 추가한 간선의 가중치 + 아직 그래프에 추가하지 않은 가중치의 총 합이 될 것이다.  따라서 각 간선을 추가할 때마다 몇 개의 쌍이 처음으로 연결이 되었는지를 알 수 있으면 문제를 해결할 수 있고, 이는 union & find에서 size를 같이 관리해줌으로서 해결할 수 있다. 총 시간복잡도는 $O(NlgN)$union & find에 대해서 알고 싶다면 이 글을 보자!

코드

#include <bits/stdc++.h>
using namespace std;
#define maxn 100005
struct edg{
    int a,b,c;
};
bool sf(edg a, edg b)
{
    return a.c<b.c;
}
edg arr[101010];
int par[101010];
int num[101010];
int uf(int a)
{
    if(par[a]==a)
        return a;
    if(par[a]==0)
    {
        par[a]=a;
        return a;
    }
    par[a]=uf(par[a]);
    return par[a];
}
bool mergee(int a,int b)
{
    a=uf(a);
    b=uf(b);
    if(a==b) return false;
    if(num[a]>num[b])
    {
        par[b]=a;
        num[a]+=num[b];
    }
    else if(num[a]<num[b])
    {
        par[a]=b;
        num[b]+=num[a];
    }
    if(num[a]==num[b])
    {
        par[a]=b;
        num[b]+=num[a];
    }
    return true;
}
int main()
{
    int n,m,i,j,k,l;
    long long int sum=0, ans=0;
    scanf("%d %d",&n,&m);
    for(i=1;i<=m;i++)
    {
        scanf("%d %d %d",&arr[i].a,&arr[i].b,&arr[i].c);
        sum+=arr[i].c;
    }
    for(i=1;i<=n;i++)
    {
        num[i]=1;
        par[i]=i;
    }
    sort(arr+1,arr+1+m,sf);
    for(i=m;i>=1;i--)
    {
        int a,b,c,aa,bb;
        a=arr[i].a;
        b=arr[i].b;
        c=arr[i].c;
        aa=uf(a);
        bb=uf(b);
        if(aa!=bb)
        {
            ans+=sum*num[aa]*num[bb];
            mergee(a,b);
        }
        sum-=c;
    }
    printf("%lld",ans%1000000000);
}