SPOJ) KOICOST

The Problem in Short : 

undirected weighted graph 가 주어진다.

Cost(u,v) 는 u와 v 상의 경로가 존재한다면 가장 작은 가중치의 edge 를 삭제한다. 이 과정중에서 삭제되는 간선들의 가중치의 합.

모든 u,v 의 순서쌍에 대해서  Cost(u,v)를 계산하는 것이다.

The Solution : 

lastedge(x,y) 를  x 와 y 를 분리할때 사용되는 마지막 edge 라고 하자.

lastedge가 e 인 정점들의 순서쌍의 걔수를 f(e) 라고 정의하자.

edgesum(u,v) 는 자기보다 작은 가중치 를 갖는 간선들의 합 이라고하자.

따라서 answer = 모든 edge에 대하여 (sum(u,v) * f(u,v) ) 들의 합이다.

f(u,v) 를 효율적으로 구해보자. 

디스조인트 셋은 undo  가 불가능 하므로 정점들을 분리하는 것이아니라 역으로

정점을 합쳐가는 방향으로 생각하자!

따라서 각 간선들을 큰 순서부터 같은 연결요소라면 sz(u) * sz(v)를 더해주고 아니라면 

continue 한다.

#include <cstdio>
#include <algorithm>
 
using namespace std;
typedef long long ll;
ll n,d;
ll a[101000];
ll maxifromend[101000];
int main(){
scanf("%lld %lld",&n,&d);
 
for(int i = 1 ; i <= n ; i++){
    scanf("%lld",&a[i]);
}
 
ll maxi = a[n];
for(int i = n ; i >=1; i--){
    maxi = max(maxi,maxi + a[i]);
    maxifromend[i] = maxi;
}
 
ll curr = 0;
bool flag = 1;
for(int i = 1; i <= n ; i++){
    if(a[i] == 0){
        
        if(d - maxifromend[i+1] < 0){
            flag = 0;
            break;
        }
        else if(){
 
        }
        else{
            curr = d - maxifromend[i+1];
        }
    }
}
printf("%d")
 
 
 
}