kmjp's blog

競技プログラミング参加記です

yukicoder : No.2915 辺更新価値最大化

そんなテクあったな…。
https://yukicoder.me/problems/no/2915

問題

N点M辺の有向グラフが与えられる。
各辺を通ると、辺に指定された満足度が加算される。
なお、満足度が正となる閉路は存在しない。

以下のクエリに答えよ。

  • 1辺の有効・無効を切り替える。
  • 頂点1から頂点Nに、有効辺を使って移動する場合の満足度の最大値を答える。

解法

N,Mが小さいので、満足度の符号反転したものをコストとみなし、毎回ダイクストラ法を使用してよい。
ただし、辺にコストがマイナスのものがあるので、それを取り除かないとTLEする。

初期状態で、各点のポテンシャルを求め、それにより辺のコストを修正して負の辺を取り除けばよい。

int N,M,T;
int U[1010],V[1010],W[1010];
int dis[1010];

vector<int> E[1010];
int dp[1010];
int P[1010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M>>T;
	FOR(i,M) {
		cin>>U[i]>>V[i]>>W[i];
		U[i]--,V[i]--;
		E[U[i]].push_back(i);
	}
	FOR(i,N) dp[i]=-1<<30;
	
	dp[0]=0;
	priority_queue<pair<int,int>> Q;
	Q.push({0,0});
	while(Q.size()) {
		int co=-Q.top().first;
		int cur=Q.top().second;
		Q.pop();
		if(co!=dp[cur]) continue;
		FORR(e,E[cur]) if(dis[e]==0 && chmax(dp[V[e]],co+W[e])) Q.push({-dp[V[e]],V[e]});
	}
	FOR(i,M) {
		W[i]=dp[V[i]]-dp[U[i]]+W[i];
	}
	
	FOR(i,N) P[i]=dp[i];
	
	while(T--) {
		cin>>x;
		dis[x-1]^=1;
		FOR(i,N) dp[i]=-1<<30;
		
		dp[0]=0;
		priority_queue<pair<int,int>> Q;
		Q.push({0,0});
		while(Q.size()) {
			int co=-Q.top().first;
			int cur=Q.top().second;
			Q.pop();
			if(co!=dp[cur]) continue;
			FORR(e,E[cur]) if(dis[e]==0 && chmax(dp[V[e]],co+W[e])) Q.push({-dp[V[e]],V[e]});
		}
		int ret=dp[N-1];
		if(ret==-1<<30) {
			cout<<"NaN"<<endl;
		}
		else {
			cout<<ret-P[N-1]<<endl;
		}
	}
}

まとめ

このテクちょくちょく忘れる。