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;
	}
};