そんなテクあったな…。
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; } } }
まとめ
このテクちょくちょく忘れる。