题解 [ABC261Ex] Game on Graph

· · 题解

考虑动态规划。f_{i,0} 表示 Takahashi 在 i 点先手时的得分，f_{i,1} 表示 Aoki 先手的得分。显然有

\begin{aligned} f_{i,0}=\min_{i\to j}f_{j,1}+w(i,j)\\ f_{i,1}=\max_{i\to j}f_{j,0}+w(i,j) \end{aligned}

如果这个有向图是个 DAG，那就非常好解决。现在这个图有环了，处理动态规划转移顺序的问题就会比较棘手。

有一种想法是在环中直接输出 INFINITY。但是样例三就否定了这个想法。尝试去改进它：

我们用类似 Dijkstra 的方法去做转移：维护一个优先队列，每当得到一个 f_{x,k} 时，就在反向图中松弛 f_{y,1-k}（存在边 x\to y）。再套用上面的更新规则往优先队列中加点即可。

时间复杂度 O(m\log n)。

#include<bits/stdc++.h>
#define ll long long
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Rof(i,a,b) for(int i=(a);i>=(b);--i)
using namespace std;
typedef pair<int,int> Pair;
const int Maxn=2e5;
const ll inf=1e18;

inline int read()
{
    char ch=getchar();
    int f=1,x=0;
    while(ch>'9' || ch<'0')
    {
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0' && ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return x*f;
}

int n,m,s,oud[Maxn+5][2];
int vis[Maxn+5][2]; ll f[Maxn+5][2];
vector<Pair> v[Maxn+5],w[Maxn+5];
struct Node{int x,y; ll z;};
bool operator<(Node a,Node b) {return a.z>b.z;}
priority_queue<Node> q;

inline void bfs()
{
    while(!q.empty())
    {
        Node k=q.top(); q.pop();
        int x=k.x,t=k.y;
        if(vis[x][t]) continue;
        vis[x][t]=1;
        for(auto i:w[x])
        {
            int y=i.first,z=i.second; oud[y][t^1]--;
            if(t==1) f[y][0]=min(f[y][0],f[x][1]+z);
            if(t==0) f[y][1]=max(f[y][1],f[x][0]+z);
            if(!oud[y][t^1]) q.push((Node){y,t^1,f[y][t^1]});
            else if(t==1) q.push((Node){y,0,f[y][0]});
        }
    }
}

int main()
{
    n=read(),m=read(),s=read();
    For(i,1,m)
    {
        int a=read(),b=read(),c=read();
        v[a].push_back(make_pair(b,c));
        w[b].push_back(make_pair(a,c));
        oud[a][0]++,oud[a][1]++;
    }
    For(i,1,n) f[i][0]=inf;
    For(i,1,n)
        if(!oud[i][0])
        {
            f[i][0]=f[i][1]=0;
            q.push((Node){i,0,0});
            q.push((Node){i,1,0});
        }
    bfs();
    if(!vis[s][0]) printf("INFINITY\n");
    else printf("%lld\n",f[s][0]);
    return 0;
}