AtCoder ARC #026 : D - 道を直すお仕事

これ系の問題苦手…。
http://arc026.contest.atcoder.jp/tasks/arc026_4

問題

N頂点・M辺からなるグラフが与えられる。
各辺にはコストC[i]及び時間T[i]が与えられている。

今、M辺すべてが壊れて利用できる。
ここで何辺か修理してN頂点を連結状態にしたい。
その場合の最小時給(コスト/時間比)を答えよ。

解法

最小比全域木という定番問題らしい。

最初、「C[i]/T[i]の小さい順にソートして使っていけば？」と思ったが、C[i]/T[i]を小さい順に使うのが最良とは限らない。
例えば途中まで処理した場合の総コストが2000、総時間が1000の場合、(C[i],T[i])=(13,10)の辺を追加すると時給は2013/1010=1.993だが、(C[i],T[i])=(135,100)の辺を追加すると時給は2135/1100=1.941であり、後者の方がC[i]/T[i]は大きいが最終的な時給は下がる。
これは後者のT[i]が大きいため、元の2000/1000の分母を大きくする効果があるためである。

求める時給をxとすると、利用する辺についてsum(C[i])<=x*sum(T[i])となるはずである。
xの下限を求める問題なので、よってxを以下の条件を満たすかどうかで二分探索していけばよい。

• 辺をC[i]-x*T[i]の値でソートする。
• C[i]-x*T[i] <= 0の辺はすべて使用してよい。これらの辺は時給がxより小さいので、全体の時給を押し下げる効果がある。
• C[i]-x*T[i] > 0の辺は、非連結の頂点を結ぶ場合のみ利用してよい。
• 最終的に利用した辺についてsum(C[i])<=x*sum(T[i])ならそのxは有効である。

class UF {
	public:
	static const int ufmax=10002;
	int ufpar[ufmax],ufrank[ufmax],ufcnt[ufmax];
	UF() { init();}
	void init(){int i; FOR(i,ufmax) { ufpar[i]=i; ufrank[i]=0; ufcnt[i]=1; } }
	int find(int x) {	return (ufpar[x]==x)?(x):(ufpar[x] = find(ufpar[x]));}
	int operator[](int x) {return find(x);}
	int count(int x) {return ufcnt[x];}
	void unite(int x,int y) {
		x = find(x); y = find(y);
		if(x==y) return;
		if(ufrank[x]<ufrank[y]) ufpar[x]=y, ufcnt[y]+=ufcnt[x];
		else {ufpar[y]=x; ufcnt[x]+=ufcnt[y]; if(ufrank[x]==ufrank[y]) ufrank[x]++;}
	}
};
 
int N,M;
int A[10001],B[10001],C[10001],T[10001];

int ok(double v) {
	int f,i,j,k,l,x,y;
	pair<double,int> P[10001];
	UF uf;
	
	FOR(i,M) P[i]=make_pair(C[i]-v*T[i],i);
	sort(P,P+M);
	
	ll TC=0,TT=0;
	FOR(i,M) {
		int f=P[i].second;
		if(P[i].first<=0 || uf[A[f]]!=uf[B[f]]) {
			uf.unite(A[f],B[f]);
			TC+=C[f];
			TT+=T[f];
		}
	}
	return TC/(double)TT <= v;
}

void solve() {
	int f,i,j,k,l,x,y;

	cin>>N>>M;
	FOR(i,M) cin>>A[i]>>B[i]>>C[i]>>T[i];
	
	double LL=0,RR=1e12;
	FOR(i,100) {
		double mi=(LL+RR)/2.0;
		if(ok(mi)) RR=mi;
		else LL=mi;
	}
	
	_P("%.6lf\n",(LL+RR)/2);
	
}

まとめ

本番、「何らかの基準で辺をソートする」「二分探索を用いる」の両アプローチは思いついたものお、二分探索の値を使ったソートは思い浮かばなかった。

実際自分はこのタイプの問題は苦手でSRMでも何度か落としている。
「何らかの基準で辺をソートする」に至った点は成長しているのだが、あとひと踏ん張りができないのが難点。

…そもそも最小比全域木自体定番アルゴリズムらしいのだが。