読者です 読者をやめる 読者になる 読者になる

JOI 2010 春合宿 day3-1 「Finals」

JOI

問題文を取り違えて悩んでた...
プリムやらクラスカルやらで最小全域木を求めて、そこから料金の高い辺から順に引いていく。

#include<cstdio>
#include<vector>
#include<queue>
#define rep(i,n) for(int i = 0; i < n; i++)
#define rrep(i,n) for(int i = 1; i <= n; i++)
#define pb push_back
#define fi first
#define se second
using namespace std;
typedef pair<int,int> P;

vector<P> e[100001];
bool used[100001];

int main(){
	int n, m, k, a, b, c, sum = 0;
	priority_queue<P, vector<P>, greater<P> > q;
	priority_queue<int> l;
	P p;
	scanf("%d%d%d",&n,&m,&k);
	
	rep(i,m){
		scanf("%d%d%d",&a,&b,&c);
		e[a].pb(P(c,b));
		e[b].pb(P(c,a));
	}
	
	rrep(i,n){
		if(!used[i]){
			q.push(P(0,i));
			while(!q.empty()){
				p = q.top(); q.pop();
				if(!used[p.se]){
					sum += p.fi;
					l.push(p.fi);
					used[p.se] = true;
					rep(j,e[p.se].size()) q.push(P(e[p.se][j].fi, e[p.se][j].se));
				}
			}
			
			k--;
		}
	}
	
	
	rep(i,k){ sum -= l.top(); l.pop();}
	
	printf("%d\n",sum);
	
	return 0;
}