題解 ABC261H【Game on Graph】
problem
Takahashi 和 Aoki 正在一張?\(n\)?個點，\(m\)?條邊的帶權(quán)有向圖上玩游戲。游戲規(guī)則如下：
有一顆最初在?\(s\)?點的棋子。雙方輪流移動這顆棋子，Takahashi 先手。
每一次移動都可以使棋子從邊的一端移動到另一端。如果無法移動，也就是不存在出邊時，游戲結(jié)束。
定義一局游戲的得分為棋子移動路徑上的邊權(quán)之和。如果經(jīng)過一條邊多次，邊權(quán)也計算多次。
Takahashi 想要最小化游戲的得分，但 Aoki 想要最大化得分。請輸出在最優(yōu)策略下游戲的最終得分。特別地，如果游戲無法結(jié)束，請輸出?INFINITY。
\(1\le n\le 2\times 10^5,\ 0\le m\le 2\times 10^5\)。有向圖保證沒有重邊和自環(huán)，但?不保證無環(huán)。
solution
考慮拆點，把圖上的點?\(u\)?拆成?\(u,u+n\)?兩個點，分別表示走到這個點時高橋 / 青木先手。那么所有的邊?\((u,v)\)?也拆成?\((u,v+n),(u+n,v)\)?兩條?？梢园l(fā)現(xiàn)這樣建出的圖是二分圖。
考慮在反圖上 DP：令?\(f_u\)?表示在這個點上的得分。
\[f_u=\begin{cases}
\min_{v}\{f_v+w_{u,v}\},\quad&(u\leq n,v>n,\text{以下稱為白點}),\\
\max_{v}\{f_v+w_{u,v}\},\quad&(u>n,v\leq n,\text{以下稱為黑點}).
\end{cases}\]
初始時所有的葉子答案為?\(0\)，最終答案?\(f_s\)。但是這個 DP 有后效性。
我們假想我們從小到大拿白點出來更新，考慮幾個貪心：
當一個白點被拿出來的時候，它一定是最小的。
感性理解：邊權(quán)非負，如果它取出來不是最小，那么最小的值應(yīng)該在后面繞回來的時候更新，這個時候已經(jīng)比取出時的大了。
當且僅當所有能更新一個黑點的白點取完后，這個黑點能更新其它白點的答案。
感性理解：不然你如何說明這個黑點取得的答案是最大值？
于是我們用一個堆放白點，從小到大取白點，用白點更新黑點，如果一個黑點已經(jīng)被完全更新，就用黑點去更新白點，將更新后的白點放入堆中。
整個算法和 Dijkstra 很像。復(fù)雜度?\(O(m\log m)\)。
code
#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
template<int N,int M,class T=int> struct graph{
? ?int head[N+10],nxt[M*2+10],cnt;
? ?struct edge{
? ? ? ?int u,v; T w;
? ? ? ?edge(int u=0,int v=0,T w=0):u(u),v(v),w(w){}
? ?} e[M*2+10];
? ?graph(){memset(head,cnt=0,sizeof head);}
? ?edge& operator[](int i){return e[i];}
? ?void add(int u,int v,T w=0){e[++cnt]=edge(u,v,w),nxt[cnt]=head[u],head[u]=cnt;}
? ?void link(int u,int v,T w=0){add(u,v,w),add(v,u,w);}
};
int n,m,s,deg[400010];
LL f[400010];
bool vis[400010];
graph<400010,400010,int> g;
priority_queue<pair<LL,int>,vector<pair<LL,int>>,greater<pair<LL,int>>> q;
void expand(int u){//u>n
for(int i=g.head[u];i;i=g.nxt[i]){
int v=g[i].v;
if(f[v]>f[u]+g[i].w) q.push({f[v]=f[u]+g[i].w,v});
}
}
LL dp(){
for(int i=1;i<=n;i++) f[i]=1e18;
for(int i=n+1;i<=n*2;i++) f[i]=-1e18;
for(int i=1;i<=n;i++) if(!deg[i]) q.push({f[i]=0,i});
for(int i=n+1;i<=n*2;i++) if(!deg[i]) f[i]=0,expand(i);
memset(vis,0,sizeof vis);
while(!q.empty()){
int u=q.top().second; q.pop();
if(vis[u]) continue; vis[u]=1;
for(int i=g.head[u];i;i=g.nxt[i]){
int v=g[i].v;
if(f[v]<f[u]+g[i].w) f[v]=f[u]+g[i].w;
if(!--deg[v]) expand(v);
}
}
return f[s];
}
int main(){
scanf("%d%d%d",&n,&m,&s);
for(int i=1,u,v,w;i<=m;i++){
scanf("%d%d%d",&u,&v,&w);
g.add(v+n,u,w),g.add(v,u+n,w);
deg[u]++,deg[u+n]++;
}
LL res=dp();
if(res<1e18) printf("%lld\n",res);
else puts("INFINITY");
return 0;
}
鏈接：https://www.dianjilingqu.com/607172.html
