boj 2463: 비용

https://www.acmicpc.net/problem/2463

2463번: 비용

u>v 일때 Cost(u,v)의 값은 언제구할 수 있을까가 관건이다.

Cost(u,v)는 vertex만 있는 그래프에서, 가장 큰 edge부터 더해나가면서 만약 parent[u]!=parent[v]이면, 그 edge부터 가장 가중치작은 edge값까지의 모든 합이 Cost(u,v) 인 것이다.

그렇다면 문제의 예제에서 6을 없애는 경우에 대해 살펴보자.

1과2가 연결되어있고(group A), 3과6이 연결된 상태(group B)에서 edge=6을 더하면, 1,2,3,6이 연결될 것이다.

이경우에는 Cost(1,3),Cost(1,6),Cost(2,3),Cost(2,6) 이 해당된다. 

A에 속한 각 원소들과 B에 속한 각 원소들을 각각 a1,a2,....al, b1,b2...,bm이라 하면, A에서는 ai보다 큰 B의 원소들의 갯수 x (6+5+4+3+2 = edge들의 6보다작은 모든것 합) 을 Cost 더해주어야 하는 것이고, B 입장에서는 bi보다 큰 A의 원소들의 갯수 x (6+5+4+3+2)를 해주어야 한다.

그렇다면 각 ai, bi는 어떻게 구할까? 사실 답은 모든 Cost를 구하는 것이므로, a1+a2+...al+b1+b2+..bm 만 알면 된다.

임의의 i,j에 대해 ai와 bj는 대소비교가 가능하므로 ai<bj인 경우에는 ai에 1을 더해주면 되는것이고, 반대의 경우에는 bj에 1을 더해주면 된다. 따라서 a1+a2+...al+b1+b2+..bm = lxm이다.

그래서 매번 edge 검사를 할때, group[parent[u]]xgroup[parent[v]]x(edge들 합) 을 더해주면 된다.

여기서 참고로, group이라 함은 한 그룹이내 원소들의 갯수이다. 이는 parent로 통일시켜주는 것이 가장 적절하다.

 

void Union(int x, int y){
  int x1=p[x], y1=p[y];
  if(x1<y1){
    p[y1]=x1;
    group[x1]+=group[y1];
    Find(y);
  }else{
    p[x1]=y1;
    group[y1]+=group[x1];
    Find(x);
  }
  return;
}

if(Find(u)!=Find(v))
	ans+=(mod(group[p[u]]*group[p[v]])*mod(sum-edge_cost));

  위 코드가 핵심이다.

밑은 전체 소스코드

 

#include<bits/stdc++.h>
#define MOD 1000000000ULL

using namespace std;

typedef unsigned long long ll;
ll n,m,x,y,w,p[100001],group[100001];
vector<pair<int,pair<int,int>>> edge;
ll s=0,ans=0;

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

void Union(int x, int y){
  int x1=p[x], y1=p[y];
  if(x1<y1){
    p[y1]=x1;
    group[x1]+=group[y1];
    Find(y);
  }else{
    p[x1]=y1;
    group[y1]+=group[x1];
    Find(x);
  }
  return;
}

ll mod(ll x){
  if(x<0) return (x+MOD)%MOD;
  return x%MOD;
}

int main(){

  for(int i=1;i<=100000;i++){
    p[i]=i;
    group[i]=1;
  }
  cin>>n>>m;
  for(int i=0;i<m;i++){
    cin>>x>>y>>w;
    s+=w;
    edge.push_back({w,{x,y}});
  }
  sort(edge.begin(),edge.end());
  reverse(edge.begin(),edge.end());
  ll tmp=0;
  for(auto &e: edge){
    int cost=e.first, u=e.second.first, v=e.second.second;
    if(Find(u)!=Find(v)){
      ans+=(mod(group[p[u]]*group[p[v]])*mod(s-tmp));
      ans=mod(ans);
      Union(u,v);
    }
    tmp += cost;
  }
  cout<<ans<<'\n';
  return 0;
}