Codeforces #447 Div2 E. Ralph and Mushrooms

これなんで入力4M整数だよ…。
http://codeforces.com/contest/894/problem/E

問題

有向グラフが与えられる。
各辺は初期値でWの値が振られている。

各辺は複数回通ることが出来、その際振られた値の分だけスコアを得ることができる。
ただし通るたびに得られるスコアはW,W-1,W-1-2,W-1-2-3,...と減少していく。
スコアは減少しても0で止まり、また0でも移動は可能である。

始点Sから辺を辿り移動していくとき、最大どれだけスコアを得られるか。

解法

閉路中にある辺は一旦その閉路に入れば何度でも通ることができる。
よってまず入力を強連結成分分解しよう。
連結成分内の辺は、縮約後の点に入れば何度でも通れることになるので、縮約後の点の獲得スコアとしてカウントする。

こうすると、DAGに対し辺と点にスコアが振られた状態に持ち込むことができる。
後はDPで最大値を求めよう。
今回入力が大きいため、DPパートでpriority_queueを使ったりするとTLEする。
幸いグラフ形状はすでにDAGなので、メモ化再帰で解くことができる。

int N,M,S;
int X[1010101],Y[1010101],W[1010101];

class SCC {
public:
	static const int MV = 1010101;
	vector<vector<int> > SC; int NV,GR[MV],rev[MV];
private:
	vector<int> E[MV], RE[MV], NUM; int vis[MV];
public:
	void init(int NV) { this->NV=NV; for(int i=0;i<MV;i++) { E[i].clear(); RE[i].clear();}}
	void add_edge(int x,int y) { E[x].push_back(y); RE[y].push_back(x); }
	void dfs(int cu) { vis[cu]=1; for(int i=0;i<E[cu].size();i++) if(!vis[E[cu][i]]) dfs(E[cu][i]); NUM.push_back(cu); }
	void revdfs(int cu, int ind) { int i; vis[cu]=1; GR[cu]=ind; SC[ind].push_back(cu); rev[cu]=ind;
		FOR(i,RE[cu].size()) if(!vis[RE[cu][i]]) revdfs(RE[cu][i],ind);}
	void scc() {
		int c=0; SC.clear(); SC.resize(MV); NUM.clear();
		ZERO(vis); for(int i=0;i<NV;i++) if(!vis[i]) dfs(i);
		ZERO(vis); for(int i=NUM.size()-1;i>=0;i--) if(!vis[NUM[i]]){
			SC[c].clear(); revdfs(NUM[i],c); sort(SC[c].begin(),SC[c].end()); c++;
		}
		SC.resize(c);
	}
};
SCC scc;

ll VW[1010101];
vector<pair<int,int>> E[1010101];

ll memo[1010101];

ll hoge(int cur) {
	if(memo[cur]>=0) return memo[cur];
	ll ret=VW[cur];
	FORR(e,E[cur]) ret=max(ret,VW[cur]+hoge(e.first)+e.second);
	return memo[cur]=ret;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	scanf("%d%d",&N,&M);
	scc.init(N);
	FOR(i,M) {
		scanf("%d%d%d",&X[i],&Y[i],&W[i]);
		X[i]--;
		Y[i]--;
		
		scc.add_edge(X[i],Y[i]);
	}
	
	scc.scc();
	FOR(i,M) {
		if(scc.GR[X[i]]==scc.GR[Y[i]]) {
			x=0;
			for(j=14;j>=0;j--) {
				y=x+(1<<j);
				if(y*(y+1)<W[i]*2) x=y;
			}
			VW[scc.GR[X[i]]]+=1LL*W[i]*(x+1)-1LL*x*(x+1)*(x+2)/6;
		}
		else {
			E[scc.GR[X[i]]].push_back({scc.GR[Y[i]],W[i]});
		}
	}
	
	scanf("%d",&S);
	MINUS(memo);
	cout<<hoge(scc.GR[S-1])<<endl;
}

まとめ

scanfとcinで気を使うの面倒で嫌い…。