TopCoder SRM 838 : Div1 Hard Forest

面倒ではあるが難しくはないな…。
https://community.topcoder.com/stat?c=problem_statement&pm=17820

問題

N頂点の無向グラフが与えられる。
各辺には重さが設定されている。

ここで、各辺がそれぞれ確率Pで消えるとする。
残されたグラフのminimum spanning forestの重さの期待値を求めよ。

解法

各点の連結状態をキーとし、その状態に至る確率及び重さを持ちながら、クラスカル法を適用していけばよい。

vector<ll> cand;
ll p10[10];
unordered_map<ll,int> M;

double fromP[30000];
double fromS[30000];
double toP[30000];
double toS[30000];
ll memo[30000][10][10];

class Forest {
	public:
	
	void dfs(int N,int cur,ll v) {
		if(cur==N) {
			cand.push_back(v);
			return;
		}
		int i;
		for(i=0;i<=cur;i++) {
			if(i<cur&&((v/p10[i])%10!=i)) continue;
			dfs(N,cur+1,v+i*p10[cur]);
		}
	}
	ll merge(ll v,int a,int b) {
		
		if(memo[M[v]][a][b]>=0) return memo[M[v]][a][b];
		ll ov=v;
		int a1=(v/p10[a])%10;
		int b1=(v/p10[b])%10;
		int m=min(a1,b1);
		int i;
		FOR(i,9) {
			int c=(v/p10[i])%10;
			
			if(c==a1||c==b1) {
				v-=c*p10[i];
				v+=m*p10[i];
			}
		}
		assert(M.count(v));
		return memo[M[ov]][a][b]=v;
	}
	
	double solve(int N, vector <int> X, vector <int> Y, vector <int> L, int P) {
		vector<pair<int,pair<int,int>>> C;
		int i;
		p10[0]=1;
		FOR(i,9) p10[i+1]=p10[i]*10;
		FOR(i,L.size()) C.push_back({L[i],{X[i],Y[i]}});
		double hit=1-P/100.0;
		
		MINUS(memo);
		
		cand.clear();
		dfs(9,0,0);
		FOR(i,cand.size()) M[cand[i]]=i;
		ZERO(fromP);
		ZERO(fromS);
		fromP[M[876543210]]=1;
		sort(ALL(C));
		FORR(c,C) {
			int l=c.first;
			int x=c.second.first;
			int y=c.second.second;
			ZERO(toP);
			ZERO(toS);
			FOR(i,cand.size()) if(fromP[i]) {
				ll a=cand[i];
				ll b=merge(cand[i],x,y);
				if(a==b) {
					toP[i]+=fromP[i];
					toS[i]+=fromP[i]*fromS[i];
				}
				else {
					toP[i]+=(1-hit)*fromP[i];
					toS[i]+=(1-hit)*fromP[i]*fromS[i];
					toP[M[b]]+=hit*fromP[i];
					toS[M[b]]+=hit*fromP[i]*(l+fromS[i]);
				}
			}
			
			swap(fromS,toS);
			swap(fromP,toP);
			FOR(i,cand.size()) if(fromP[i]) fromS[i]/=fromP[i];
		}
		
		double ret=0;
		FOR(i,cand.size()) ret+=fromS[i]*fromP[i];
		
		return ret;
		
	}
}

まとめ

TLEが怖くて連結状態の管理をかなり慎重にやったので、だいぶコーディングに手間取ってしまった。
連結状態はベル数で抑えられてあまり大きくないので、割と雑でもTLEしないようだ。