TopCoder SRM 584 Div1 Hard FoxTheLinguist
問題
n個の言語をマスターしたい。
最初はすべてレベル0で、9になったらマスター。
m個の講習を受けることができて、i番目の講習は、
言語a[i]のレベルがb[i]以上のときに、言語c[i]のレベルをd[i]まで上げることができて、e[i]の時間がかかる。
全ての言語をマスターするのにかかる時間の最小値を求めよ。
制約条件
n≦10
m≦150
方針
なんかA*で通りそうだったから適当にA*したら通った。完全なる嘘解法。
こんだけクソコード書いたのに奇跡的に実装が全くバグらなかった。
今からeditorial読む。
読んだ。どうみても有向最小全域木です。頭悪すぎた。
てかこれ系の完全に同じ問題絶対解いたことあるでしょ。
ソースコード
#define F first #define S second int p[10]; int root(int x){ if(x == p[x]) return x; return p[x] = root(p[x]); } class FoxTheLinguist { public: int minimalHours(int n, vector <string> courseInfo) { vector<pair<pi, int> > e; string s; rep(i, courseInfo.size()) s += courseInfo[i]; stringstream ss(s); while(ss >> s){ char a, b, c, d; int f; sscanf(s.c_str(), " %c%c->%c%c:%d", &a, &b, &c, &d, &f); e.pb(mp(mp((a - 'A') * 10 + b - '0', (c - 'A') * 10 + d - '0'), f)); } if(!can(n, e)) return -1; vi er; sort(all(e)); e.erase(unique(all(e)), e.end()); rep(i, e.size()) rep(j, e.size()) if(i != j){ if(e[i].F.F / 10 != e[j].F.F / 10 || e[i].F.S / 10 != e[j].F.S / 10) continue; if(e[i].F.F % 10 > e[j].F.F % 10 || e[i].F.S % 10 < e[j].F.S % 10) continue; if(e[i].S > e[j].S) continue; er.pb(j); } sort(all(er)); er.erase(unique(all(er)), er.end()); for(int i = (int)er.size() - 1; i >= 0; i--) e.erase(e.begin() + er[i]); rep(i, e.size()) cerr<<e[i].F.F/10<<" "<<e[i].F.F%10<<" "<<e[i].F.S/10<<" "<<e[i].F.S%10<<" "<<e[i].S<<endl; rep(i, n) p[i] = i; rep(i, e.size()){ int a = e[i].F.F / 10, b = e[i].F.S / 10; a = root(a); b = root(b); if(a == b) continue; p[b] = a; } bool useroot[10] = {}; int ans = 0; rep(i, n){ int r = root(i); if(useroot[r]) continue; useroot[r] = 1; vi vs; rep(j, n) if(root(j) == r) vs.pb(j); sort(all(vs)); vector<pair<pi, int> > cur_e; rep(j, e.size()) if(root(e[j].F.F / 10) == r){ int a = e[j].F.F / 10, b = e[j].F.F % 10; int c = e[j].F.S / 10, d = e[j].F.S % 10; a = lower_bound(all(vs), a) - vs.begin(); c = lower_bound(all(vs), c) - vs.begin(); cur_e.pb(mp(mp(a * 10 + b, c * 10 + d), e[j].S)); } ans += solve(vs.size(), cur_e); } return ans; } inline int solve(int n, const vector<pair<pi, int> > &e){ priority_queue<pair<pi, vi> > q; vi v(n); set<vi> vis; q.push(mp(mp(-estimate(n, e, v), 0), v)); while(!q.empty()){ int cost = q.top().F.S; v = q.top().S; q.pop(); if(vis.count(v)) continue; vis.insert(v); bool ok = 1; rep(i, n) if(v[i] < 9) ok = 0; if(ok) return -cost; //use zero cost edge rep(i, e.size()) if(v[e[i].F.F / 10] >= e[i].F.F % 10 && v[e[i].F.S / 10] < e[i].F.S % 10 && e[i].S == 0){ int nc = cost - e[i].S; vi nv = v; nv[e[i].F.S / 10] = e[i].F.S % 10; if(!vis.count(nv)) q.push(mp(mp(-estimate(n, e, nv) + nc, nc), nv)); goto END; } rep(i, e.size()) if(v[e[i].F.F / 10] >= e[i].F.F % 10 && v[e[i].F.S / 10] < e[i].F.S % 10){ int nc = cost - e[i].S; vi nv = v; nv[e[i].F.S / 10] = e[i].F.S % 10; if(!vis.count(nv)) q.push(mp(mp(-estimate(n, e, nv) + nc, nc), nv)); } END:; } return -2; } inline int estimate(int n, const vector<pair<pi, int> > &e, const vi &v){ int res = 0; int mn[10]; rep(i, n) mn[i] = v[i] < 9 ? inf : 0; rep(i, e.size()){ if(v[e[i].F.S / 10] < 9 && e[i].F.S % 10 == 9) mn[e[i].F.S / 10] = min(mn[e[i].F.S / 10], e[i].S); } rep(i, n) res += mn[i]; return res; } inline bool can(int n, const vector<pair<pi, int> > &e){ int level[10] = {}; while(1){ bool update = 0; rep(i, e.size()){ if(level[e[i].F.F / 10] >= e[i].F.F % 10 && level[e[i].F.S / 10] < e[i].F.S % 10){ update = 1; level[e[i].F.S / 10] = e[i].F.S % 10; } } if(!update) break; } rep(i, n) if(level[i] < 9) return 0; return 1; } };