WUPC2nd E - 独立記念日

問題

日本語なので本文参照（http://wupc2nd.contest.atcoder.jp/tasks/wupc_05）

閉路を高々1つ含む、重みつき無向グラフが与えられる。
このグラフの辺をいくつか切断して、グラフがk個以上の連結成分に分かれるようにしたい。

切断する辺の重みの和の最小値はいくつか。

制約条件

グラフの頂点≦100
辺≦100

方針

閉路の辺を切断する場合、しない場合で場合分け。

閉路の辺を切断する場合、切断する辺をひとつ決めるとグラフは森になる。
なので、森はひとつ辺を切断するたびに連結成分の個数は1つ増えるので、
貪欲にコストの安い辺から切断すればいい。

閉路の辺を切断しない場合、閉路以外の辺を1本切断すれば、連結成分の個数は1増えるので
コストの安い辺から切断すればいい。

ちなみに、閉路が任意の個数含まれている問題はNP困難であるらしい。
証明を考えてみたけど、うまく示せなかった。。。

ソースコード

int p[100];
int root(int x){
	if(x == p[x]) return x;
	return p[x] = root(p[x]);
}
int n, m, k;
vector<pair<int, pi> > es;
vector<vector<pi> > e; //to, id
int id[100][100];
 
bool v[100];
int st[110], sz;
bool isloop[10000];
vi loop;
 
void rec(int c, int p){
	v[c] = 1;
	st[sz++] = c;
	rep(i, e[c].size()) if(p != e[c][i].first){
		if(v[e[c][i].first] && loop.empty()){
			for(int j = sz - 1; j >= 0; j--){
				loop.pb(st[j]);
				if(st[j] == e[c][i].first) break;
			}
		}
		else if(!v[e[c][i].first]){
			rec(e[c][i].first, c);
		}
	}
	sz--;
}
 
int main(){
	cin >> n >> m >> k;
	e.resize(n);
	memset(id, -1, sizeof(id));
	int cnt = n;
	rep(i, n) p[i] = i;
	
	rep(i, m){
		int a, b, c;
		cin >> a >> b >> c;
		a--; b--;
		es.pb(mp(c, mp(a, b)));
		e[a].pb(mp(b, i));
		e[b].pb(mp(a, i));
		id[a][b] = id[b][a] = i;
		
		a = root(a);
		b = root(b);
		if(a != b){
			cnt--;
			p[a] = b;
		}
	}
	k = max(0, k - cnt);
	
	rep(i, n) if(!v[i]){
		sz = 0;
		rec(i, i);
	}
	/*
	dbg(loop.size());
	rep(i, loop.size()) dbg(loop[i]);
	*/
	
	vi edge;
	rep(i, loop.size()){
		edge.pb(id[loop[i]][loop[(i + 1) % loop.size()]]);
		isloop[edge.back()] = 1;
		assert(edge.back() >= 0);
	}
	
	ll ans = 1ll << 60;
	rep(i, edge.size()){
		ll tmp = es[edge[i]].first;
		
		vi ee;
		rep(j, m) if(edge[i] != j) ee.pb(es[j].first);
		sort(all(ee));
		rep(j, k) tmp += ee[j];
		ans = min(ans, tmp);
	}
	ll tmp = 0;
	vi ee;
	rep(i, m) if(!isloop[i]) ee.pb(es[i].first);
	sort(all(ee));
	if(ee.size() < k) tmp = 1ll << 60;
	else rep(i, k) tmp += ee[i];
	
	ans = min(ans, tmp);
	cout << ans << endl;
	
	return 0;
}