题解 P4042 【[AHOI2014/JSOI2014]骑士游戏】

· · 题解

怎么都是Spfa啊

万一挂了怎么办

虽然我也不知道这种建模跑spfa到底会怎么样

我们考虑记dp[i]表示第i个怪物被消灭的代价

显然有直接跑dp它会有后效性

较为常见的取消dp后效性的方法是按照某个值排序

在这道题中就是按照dp值排序

我们先考虑dp的转移式：

dp_i=\min(K_i,S_i+\sum_{j=1}^{R_i}dp_{v_j})

于是显然有：

dp_i$能从第二个式子转移当且仅当对于任意的$dp_{v_j}$有$dp_{v_j}<dp_i

于是我们对dp值建一个堆，令每个点的初始dp值为K_i，然后每次弹出一个dp值令其去更新其他的dp值即可

如果被更新的dp值已经更新完了，就把它加入堆内即可

如果其需要更新的dp值已经被弹出，那么显然有那个dp值小于当前dp值所以更新无用

复杂度O(n\log n+\sum R_i)

// luogu-judger-enable-o2
#include<bits/stdc++.h>
using namespace std;
#define rep( i, s, t ) for( register int i = s; i <= t; ++ i )
#define re register
#define int long long
int read() {
    char cc = getchar(); int cn = 0, flus = 1;
    while(cc < '0' || cc > '9') {  if( cc == '-' ) flus = -flus;  cc = getchar();  }
    while(cc >= '0' && cc <= '9')  cn = cn * 10 + cc - '0', cc = getchar();
    return cn * flus;
}
const int N = 2e5 + 5 ; 
const int M = 1e6 + 5 ; 
int n, s[N], K[N], dp[N], vis[N], ans[N], R[N] ;
vector<int> mp[N] ; 
struct node {
    int id, w ; 
    bool operator < ( const node& x ) const {
        return w > x.w ; 
    }
};
priority_queue<node> q ; 
signed main()
{
    n = read() ; int x, siz ; 
    rep( i, 1, n )  {
        s[i] = read(), K[i] = read(), R[i] = read() ;
        rep( j, 1, R[i] ) x = read(), mp[x].push_back(i) ; 
        q.push((node){ i, K[i] }), dp[i] = s[i] ;
    }
    while( !q.empty() ) {
        int u = q.top().id, w = q.top().w ; q.pop() ; 
        if( vis[u] ) continue ; 
        vis[u] = 1, ans[u] = w, siz = mp[u].size() - 1 ; 
        rep( i, 0, siz ) {
            int v = mp[u][i] ; 
            if( vis[v] || dp[v] > K[v] ) continue ; 
            R[v] --, dp[v] += w ;
            if( R[v] == 0 ) q.push((node){ v, dp[v] }) ;
        }
    }
    printf("%lld\n", ans[1] ) ;
    return 0;
}

这个做法的本质和Dij是一样的