Codeforces #474 F. Pathwalks

実装はちょっと面倒だけど、考え方はEより簡単。
http://codeforces.com/contest/960/problem/F

問題

N頂点M辺の有向グラフが与えられる。
各辺は重さを持つ。

以下の条件を満たす最長パスの長さを求めよ。

• 利用する辺の順番は、入力の順番である。
• 利用する辺の重さは、真に単調増加である。

解法

前者の条件より、1本ずつ辺を追加していくしかない。
そこで、各頂点について(最後に利用した辺の重さ, パス長)の集合を管理しよう。
前者が大きくなるほど後者も大きくなるよう、この集合の中身が単調増加になるよう管理する。
この集合を二分探索することで、新たな辺が追加されたとき、遷移元において最後の利用した辺の重さが新たな辺の重さに最も近いケースのみを考慮すればよくなる。

int N,M;
map<int,int> V[101010];
int ma=0;
void add(int U,int W,int num) {
	auto it=V[U].lower_bound(W+1);
	it--;
	
	if(it->second>=num) return;
	V[U][W]=num;
	while(1) {
		auto it=V[U].lower_bound(W+1);
		if(it==V[U].end()) break;
		if(it->second>num) break;
		V[U].erase(it);
	}
	
}

void solve() {
	int i,j,k,l,r,x,y,w; string s;
	
	cin>>N>>M;
	FOR(i,N) V[i][-1]=0;
	FOR(i,M) {
		cin>>x>>y>>w;
		x--,y--;
		auto it=V[x].lower_bound(w);
		it--;
		ma=max(ma,it->second+1);
		add(y,w,it->second+1);
	}
	cout<<ma<<endl;
	
}

まとめ

こういう2値のペアの最大値を保つmapの管理、ライブラリにしておいた方が楽かもなぁ。