Felix Halim .NET :: Pembahasan penyisihan INC 2007 Problem H

Diberikan suatu graph berbentuk tree. Graph ini memiliki N (1 <= N <= 10000) nodes dan N-1 edges yang mempunyai weight W (1 <= W <= 100). Carilah satu dari N node untuk dijadikan "root" sehingga total distance dari root ke semua nodes adalah minimum. Untuk contoh jelasnya (dipandu dengan gambar) silahkan lihat problem statement diatas.

Salah satu cara menyelesaikannya adalah dengan bruteforce, yaitu dengan mencoba satu-persatu node untuk dijadikan "root" dan menghitung total distance dari root tersebut ke semua nodes. Kendalanya adalah bagaimana cara menghitung total distance dari root ke semua node dalam O(1)? Berikut adalah cara yang saya ketahui, yaitu dengan menggeser root yang sekarang ke node tetangganya dan meng-update total distance ke semua nodes. Dibawah adalah langkah-langkah untuk melakukannya:

Kedua code menggunakan STL map, set, vector. Kalau tidak, maka codingnya akan jauh lebih panjanggggg..... Anda bisa menggunakan problem ini untuk belajar STL maupun rekursi dengan stack buatan.

Untuk Andrian Kurniady: sharing donk algo "DP problem I" nya gimana? pake rekursi topdown? apa bottom up?

#include <stdio.h>
#include <string.h>
#include <set>
#include <map>
#include <vector>
#include <algorithm>

using namespace std;

#define FOREACH(it,arr) for (__typeof((arr).begin()) it=(arr).begin(); it!=(arr).end(); it++)

vector<map<int,int> > con;
vector<long long> dist;
vector<int> cnt;
long long res;
int n;

void calcCnt(int i, int p){
    cnt[i]++;
    dist[i] = 0;
    FOREACH(it,con[i]){
        int j = it->first;
        int w = it->second;
        if (j!=p){
            calcCnt(j,i);
            cnt[i] += cnt[j];
            dist[i] += cnt[j] * w + dist[j];
        }
    }
}

void rec(int i, int p, int c, long long v){
    long long sum = (p==-1)? 0 : (v + c * con[p][i]);
    FOREACH(it,con[i]){
        int j = it->first;
        int w = it->second;
        if (j!=p) sum += cnt[j] * w + dist[j];
    }
    res <?= sum;

    FOREACH(it,con[i]){
        int j = it->first;
        int w = it->second;
        if (j!=p) rec(j, i, n-cnt[j], sum-(dist[j] + cnt[j]*w));
    }
}

int main(){
    while (scanf("%d",&n)!=EOF && n){
        con = vector<map<int,int> >(n);
        for (int i=1,a,b,w; i<n; i++){
            scanf("%d %d %d",&a,&b,&w);
            con[a][b] = w;
            con[b][a] = w;
        }

        cnt = vector<int>(n);
        dist = vector<long long>(n);
        calcCnt(0,-1);

        res = 1000000000000LL;
        rec(0,-1,0,0);
        printf("%lld\n",res);
    }
}

#include <stdio.h>
#include <string.h>
#include <set>
#include <map>
#include <vector>
#include <algorithm>

using namespace std;

#define FOREACH(it,arr) for (__typeof((arr).begin()) it=(arr).begin(); it!=(arr).end(); it++)

vector<map<int,int> > con;
vector<long long> dist;
vector<int> cnt;
long long res;
int n;

void calcCnt(int i, int p){
    vector<pair<int,int> > stk;
    vector<bool> vis;
    stk.push_back(make_pair(i,p));
    vis.push_back(false);
    while (stk.size()>0){
        i = stk.back().first;
        p = stk.back().second;

        if (!vis.back()){
            vis.back() = true;
            FOREACH(it,con[i]){
                int j = it->first;
                int w = it->second;
                if (j!=p){
                    stk.push_back(make_pair(j,i));
                    vis.push_back(false);
                }
            }
        } else {
            cnt[i] = 1;
            dist[i] = 0;
            FOREACH(it,con[i]){
                int j = it->first;
                int w = it->second;
                if (j!=p){
                    cnt[i] += cnt[j];
                    dist[i] += cnt[j] * w + dist[j];
                }
            }
            stk.pop_back();
            vis.pop_back();
        }
    }
}

struct ipcv {
    long long i,p,c,v;
};

void rec(int i, int p, int c, long long v){
    vector<ipcv> stk;
    vector<bool> vis;
    stk.push_back((ipcv){i,p,c,v});
    vis.push_back(false);
    while (stk.size()>0){
        ipcv t = stk.back();
        i = t.i;
        p = t.p;
        c = t.c;
        v = t.v;

        if (!vis.back()){
            vis.back() = true;

            long long sum = (p==-1)? 0 : (v + c * con[p][i]);
            FOREACH(it,con[i]){
                int j = it->first;
                int w = it->second;
                if (j!=p) sum += cnt[j] * w + dist[j];
            }
            res <?= sum;

            FOREACH(it,con[i]){
                int j = it->first;
                int w = it->second;
                if (j!=p){
                    stk.push_back((ipcv){j, i, n-cnt[j], sum-(dist[j] + cnt[j]*w)});
                    vis.push_back(false);
                }
            }
        } else {
            stk.pop_back();
            vis.pop_back();
        }
    }
}

int main(){
    while (scanf("%d",&n)!=EOF && n){
        con = vector<map<int,int> >(n);
        for (int i=1,a,b,w; i<n; i++){
            scanf("%d %d %d",&a,&b,&w);
            con[a][b] = w;
            con[b][a] = w;
        }

        cnt = vector<int>(n);
        dist = vector<long long>(n);
        calcCnt(0,-1);

        res = 1000000000000LL;
        rec(0,-1,0,0);
        printf("%lld\n",res);
    }
}

Problem H - Tree Median