[ABC261Ex] Game on Graph 题解

· · 题解

主要来说明一下正确性。

一

转移方程就不写了，大家都会，和其他题解相同，因为不是 DAG，无法直接 dp。这时候一般会考虑使用最短路算法进行转移，但要求是转移都是同号的，如都是 \max 或者都是 \min，但在这题的转移当中，同时需要取 \max,\min，而这是 Dijkstra 无法处理的。

如果我们直接丢到 Dijkstra 里面去做，显然会错，因为我们可能把还没有决策完的一个 f_{u,1}=x 丢到堆里，但实际上 f_{u,1}=y>x，然后在后续的更新中，我们用较小的 x 去更新了 f_{v,0}，这显然是不合法的。

按照上面的过程，我们希望对于 f_{u,1} 能在取完最大值后再去更新其他点，而 f_{u,0} 则可以直接更新别的点。

为什么是对的呢，因为我们这样操作，相当于做了一步确定主元，我们是以 f_{u,0} 为主元，算法的目标就是获得所有正确的 f_{u,0}，而 f_{u,1} 则是辅助我们转移的。因此可以将整个过程看成对 f_{u,0} 求最短路（实际上我们就是在求最短路），而有引理：Dijkstra 算法中，取出的结点 u 最短路均已经被确定，即满足 D(u) = dis(u)。这个可以通过反证法证明，具体见 oi-wiki 最短路 正确性证明。因此我们每次拿出去转移 f_{u,0} 的值都是正确的，而因此更新的 f_{v,1} 也是正确的，不会出现类似的用未取到最小的 f_{u,0} 去给 f_{v,1} 取 \max，而这样当我们能更新 f_{v,1} 的全部更新之后，f_{v,1} 就是确定且正确的了，这时候我，再把它丢到堆里面，去更新以后的 f_{u,0}。

我们使用了类似递归证明的方法，而这个递归证明是有边界的（出度为 0 的点已确定），这样，我们证明了这一做法的正确性。所以，这并不是所谓的魔改或者是玄学或是感性理解，这是可以证明且确定的。

复杂度 O(m\log m)。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#define int long long
using namespace std;

int n,m,S;
int ind[200005];
int f[200005][2];
bool vis[200005][2];
struct node{int u,ok,d;};
bool operator < (node p,node q){return p.d>q.d;}
priority_queue <node> q;
vector <pair <int,int>> g[200005];

signed main(){
    scanf("%lld%lld%lld",&n,&m,&S);
    for(int i=1;i<=m;i++){
        int u,v,w;
        scanf("%lld%lld%lld",&u,&v,&w);
        g[v].push_back({u,w});
        ind[u]++;
    }
    for(int i=1;i<=n;i++)
        if(ind[i]==0) q.push({i,0,0}),q.push({i,1,0});
        else f[i][0]=1e18;
    while(!q.empty()){
        auto tmp=q.top();
        q.pop();
        if(vis[tmp.u][tmp.ok]) continue;
        vis[tmp.u][tmp.ok]=1;
        int u=tmp.u,ok=tmp.ok;
        for(auto tmp:g[u]){
            int v=tmp.first,w=tmp.second;
            if(!ok){
                ind[v]--;
                f[v][1]=max(f[v][1],f[u][0]+w);
                if(!ind[v]) q.push({v,1,f[v][1]});
            }
            else{
                if(f[v][0]>f[u][1]+w){
                    f[v][0]=f[u][1]+w;
                    if(!vis[v][0]) q.push({v,0,f[v][0]});
                }
            }
        }
    }
    if(f[S][0]==1e18) puts("INFINITY");
    else printf("%lld\n",f[S][0]);

    return 0;
}