problem

Takahashi 和 Aoki 正在一张 \(n\) 个点，\(m\) 条边的带权有向图上玩游戏。游戏规则如下：

• 有一颗最初在 \(s\) 点的棋子。双方轮流移动这颗棋子，Takahashi 先手。

• 每一次移动都可以使棋子从边的一端移动到另一端。如果无法移动，也就是不存在出边时，游戏结束。

• 定义一局游戏的得分为棋子移动路径上的边权之和。如果经过一条边多次，边权也计算多次。

Takahashi 想要最小化游戏的得分，但 Aoki 想要最大化得分。请输出在最优策略下游戏的最终得分。特别地，如果游戏无法结束，请输出 INFINITY。

\(1\le n\le 2\times 10^5,\ 0\le m\le 2\times 10^5\)。有向图保证没有重边和自环，但 不保证无环。

solution

考虑拆点，把图上的点 \(u\) 拆成 \(u,u+n\) 两个点，分别表示走到这个点时高桥 / 青木先手。那么所有的边 \((u,v)\) 也拆成 \((u,v+n),(u+n,v)\) 两条。可以发现这样建出的图是二分图。

考虑在反图上 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 有后效性。

我们假想我们从小到大拿白点出来更新，考虑几个贪心：

1. 当一个白点被拿出来的时候，它一定是最小的。

感性理解：边权非负，如果它取出来不是最小，那么最小的值应该在后面绕回来的时候更新，这个时候已经比取出时的大了。

1. 当且仅当所有能更新一个黑点的白点取完后，这个黑点能更新其它白点的答案。

感性理解：不然你如何说明这个黑点取得的答案是最大值？

于是我们用一个堆放白点，从小到大取白点，用白点更新黑点，如果一个黑点已经被完全更新，就用黑点去更新白点，将更新后的白点放入堆中。

整个算法和 Dijkstra 很像。复杂度 \(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