[JOI合宿]2010-Day3:Finals

呼んだ瞬間最小全域木から幾つか辺を抜く問題だと思ったけど, 頭の中でサンプルの全域木を書いたら間違っていて絶望していました.
実際ちゃんとやったらそのとおりで簡単.

O(MlogN)程度です.

問題文 : http://qnighy.github.com/informatics-olympiad/joi2010-day3-finals-problem.html
昔MSTはprimとか書いてた気がしますが, kruskalの方が直感的で書きやすくなってきています.

#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
static const double EPS = 1e-5;
typedef long long ll;

typedef struct {
    int from, to;
    int cost;
} Edge;

vector<Edge> all;

int par[100000];

void init(int n)
{
    for (int i = 0; i < n; i++){
        par[i] = i;
    }
}

int find(int x)
{
    if (x == par[x]){
        return (x);
    }
    return (par[x] = find(par[x]));
}

bool same(int p, int q)
{
    return (find(p) == find(q));
}

void unite(int p, int q)
{
    p = find(p);
    q = find(q);
    if (p != q){
        par[q] = p;
    }
}

bool operator < (const Edge &a, const Edge &b)
{
    return (a.cost < b.cost);
}

int main()
{
    int N, M, K;
    scanf("%d %d %d", &N, &M, &K);
    
    for (int i = 0; i < M; i++){
        int p, q, c;
        scanf("%d %d %d", &p, &q, &c);
        Edge t;
        t.from = p, t.to = q, t.cost = c;
        all.push_back(t);
    }
    
    sort(all.begin(), all.end());
    int res;
    int count;
    res = count = 0;
    
    init(N);
    for (int i = 0; i < M; i++){
        if (count == N - K){
            break;
        }
        if (!same(all[i].to, all[i].from)){
            res += all[i].cost;
            unite(all[i].to, all[i].from);
            count++;
        }
    }
    
    printf("%d\n", res);
    
    return (0);
}