第2回早稲田大学プログラミングコンテスト E - 独立記念日
解法はすぐわかったけどめっちゃバグらせまくりました…
解法
閉路がない場合を考えます。
この場合は, 辺を一本切るごとに独立したグループが一つ増えるので, コストが小さい順に貪欲に辺を切っていって大丈夫です。
閉路がある場合は, 2 通りの場合が生じます。
閉路から何本か辺を切る場合
この場合は, 上と同じように考えればいけます。
閉路から一本も辺を切らない場合
閉路を一つのまとまった頂点と見ると, (サイクル長が C として)頂点が N-C+1 個あることになります。このグラフについて, 上と同じように貪欲に辺を切っていけば良いです。
問題を解く前提に, 閉路検出がありますが, これは以前にやりました。
mayokoex.hatenablog.com
struct Edge { int u; int v; int cost; Edge() {} Edge(int u, int v, int cost) : u(u), v(v), cost(cost) {} bool operator<(const Edge& rhs) const {return cost < rhs.cost;} }; ll calc(vector<Edge> es, int N, int K) { sort(es.begin(), es.end()); int M = es.size(); ll ret = 0; int need = max(0, M-(N-K)); for (int i = 0; i < need; i++) ret += es[i].cost; return ret; } int main() { cin.tie(0); ios::sync_with_stdio(false); int N, M, K; cin >> N >> M >> K; vector<Edge> es(M); vector<vector<Edge>> G(N); vector<int> degree(N); for (int i = 0; i < M; i++) { cin >> es[i].u >> es[i].v >> es[i].cost; es[i].u--; es[i].v--; G[es[i].u].push_back(es[i]); G[es[i].v].push_back(es[i]); degree[es[i].u]++; degree[es[i].v]++; } queue<int> que; for (int i = 0; i < N; i++) { if (degree[i] == 1) { que.push(i); degree[i] = 0; } } while (!que.empty()) { int now = que.front(); que.pop(); for (Edge e : G[now]) { int ch = (e.u == now ? e.v : e.u); if (degree[ch] == 0) continue; if (--degree[ch] == 1) { degree[ch] = 0; que.push(ch); } } } vector<int> cycle; for (int i = 0; i < M; i++) { Edge e = es[i]; if (degree[e.u] > 0 && degree[e.v] > 0) { cycle.push_back(i); } } ll ans = 1ll<<55; if (cycle.empty()) { ans = calc(es, N, K); } else { for (int c : cycle) { vector<Edge> tmp; for (int i = 0; i < M; i++) if (i != c) { tmp.push_back(es[i]); } ans = min(ans, es[c].cost + calc(tmp, N, K)); } int C = cycle.size(); if (N-C+1 >= K) { vector<Edge> tmp; for (int i = 0; i < M; i++) if (find(cycle.begin(), cycle.end(), i) == cycle.end()) { tmp.push_back(es[i]); } sort(tmp.begin(), tmp.end()); ll unko = 0; // 消す本数 int need = max(0, M-C - (N-C-K+1)); for (int i = 0; i < need; i++) unko += tmp[i].cost; ans = min(ans, unko); } } cout << ans << endl; return 0; }