Codeforces #261 Div2 E. Pashmak and Graph

アプローチはすぐ思いついたけど有向と無向を間違えて2WA…。
http://codeforces.com/contest/459/problem/E

問題

N点M有向辺からなるグラフが与えられる。
各グラフには重みが付けられている。

このグラフについて任意の頂点から辺をたどって頂点群を訪問していきたい。
この時、たどった辺の重みが真に単調増加になるような最大頂点数はいくつか。

解法

各頂点に、重みが単調増加となる辺を使いその頂点に至る最大頂点数を保持し、小さな重みの辺の順にDPしていけばよい。
辺を重み順にまともにソートすればO(N+MlogM)だが、重みの上限が小さいことを用いてビンソートで済ませればO(N+M)で済む。

同じ重みの辺が複数ある場合、それらを連続でたどらないように注意。

int N,M;
int U[300055],V[300055],W[300055];
vector<pair<int,int> > E[100005];
int ma[300005][2];

void solve() {
	int f,i,j,k,l,x,y;
	
	cin>>N>>M;
	FOR(i,M) {
		cin>>U[i]>>V[i]>>W[i];
		E[W[i]].push_back(make_pair(U[i]-1,V[i]-1));
	}
	FOR(i,100001) {
		FOR(j,E[i].size()) {
			int cur=E[i][j].first,tar=E[i][j].second;
			ma[cur][1]=ma[cur][0];
		}
		FOR(j,E[i].size()) {
			int cur=E[i][j].first,tar=E[i][j].second;
			if(ma[cur][1]+1>ma[tar][0]) ma[tar][0]=ma[cur][1]+1;
		}
	}
	int ret=0;
	FOR(i,N) ret=max(ret,max(ma[i][0],ma[i][1]));
	cout << ret << endl;
	
}

まとめ

なんで本番無向辺だと思ってしまったんだろう。