ABC261H Game on Graph

题面

简化题意

A,B 博弈。有一个有向图，$S$ 点有一个棋子，A 先手。每次可以把棋子移到另一个点上。一局游戏的博弈为棋子经过的边权和。A 想要让分数最小；B 要最大。求最后得分，或判断游戏无法结束。

$n,m\leq 2\times 10^5$。

题解

不妨先假设原图是一个 DAG。这种情况下游戏显然一定会结束。考虑 DP 设 $f_{i,0/1}$ 表示当前棋子在 $i$ 节点，A 先手或 B 先手的情况下的得分。

转移是显然的，按照两人的策略有：

$f_{u,1} = \max f_{v,0} + w$

$f_{u,0} = \min f_{v,1} + w$

考虑有环的情况。

是否只要有环，游戏就一定无法结束？

考虑下面这样的图：

初始棋子在 $1$ 节点。然后 A 将其移动到 $2$。因为 B 希望分数最大所以移动到 $3$，A 移动到 $1$，B 移动到 $2$。注意此时 A 希望分数最小，因此他不会继续这样的循环，而是将棋子移动到 $4$ 结束游戏。最终的分数是 $5$。

像这样存在环的话，DP 无法正常转移。考虑这个 DP 在什么情况下可以转移：

• $f_{i,0}$ 只需要满足后继状态中有至少一个是确定的就可以更新它。
• $f_{i,1}$ 需要满足后续状态有求出来了才可以更新。

考虑用类似最短路的方式。在反向图上 dijkstra，每次求出一个点 $f_{u,op}$ 的状态时，用它更新 $f_{v,1-op}$ 即可。

代码

#include<bits/stdc++.h>
#define int long long
#ifdef DEBUG
#   define debug(...) fprintf(stderr,__VA_ARGS__)
#else
#   define debug
#endif
using namespace std;
bool Begin;
const int max_n=200005,inf=1000000000000015LL;
inline int read(){
    int x=0;bool w=0;char c=getchar();
    while(!isdigit(c)) w|=c=='-',c=getchar();
    while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=getchar();
    return w?-x:x;
}
inline void write(int x){
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10^48);
}
struct Graph{
    int hd[max_n],to[max_n],nx[max_n],ln[max_n],ct;
    Graph(){ct=1;}
    inline void add(int u,int v,int w){
        nx[++ct]=hd[u],hd[u]=ct,to[ct]=v,ln[ct]=w;
    }
}e;

int n,m,S,f[max_n][2],deg[max_n];

struct node{
    int u,op,x;
    node(int U=0,int OP=0,int X=0):u(U),op(OP),x(X){}
    bool operator < (const node &b) const{
        node a=*this;
        if(a.x==b.x && a.u==b.u) return a.op<b.op;
        if(a.x==b.x) return a.u<b.u;
        return a.x>b.x;
    }
};
function<void(int&,int)> F[2]={
    [](int &x,int y){x=min(x,y);},
    [](int &x,int y){x=max(x,y);}
};
bool vis[max_n][2];
priority_queue<node> q;
inline void dijs(){
    for(int i=1;i<=n;++i)
        f[i][0]=inf,f[i][1]=-inf;
    for(int i=1;i<=n;++i) if(!deg[i]){
        f[i][0]=f[i][1]=0;
        q.emplace(i,0,0);
        q.emplace(i,1,0);
    }
    while(!q.empty()){
        int u=q.top().u,op=q.top().op;q.pop();
        if(vis[u][op]) continue;
        vis[u][op]=1;
        for(int i=e.hd[u];i;i=e.nx[i]){
            int v=e.to[i],w=e.ln[i];
            F[op^1](f[v][op^1],f[u][op]+w);
            if(op || !(--deg[v]))
                q.emplace(v,op^1,f[v][op^1]);
        }
    }
}

bool End;
#define File ""
signed main(){
    #ifndef ONLINE_JUDGE
    freopen(File ".in","r",stdin);
    freopen(File ".out","w",stdout);
    #endif
    debug("Memory : %lf\n",(&Begin-&End)/1024.0/1024);
    n=read(),m=read(),S=read();
    for(int i=1;i<=m;++i){
        int u=read(),v=read(),w=read();
        e.add(v,u,w);
        ++deg[u];
    }
    dijs();
    if(vis[S][0]) write(f[S][0]);
    else puts("INFINITY");
    return 0;
}