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