自动搬运

查看原文

来自洛谷，原作者为

	Soulist 再见了

搬运于2025-08-24 21:55:51，当前版本为作者最后更新于2019-08-31 11:12:44，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

怎么都是Spfa啊

万一挂了怎么办

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

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

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

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

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

我们先考虑$dp$的转移式：

于是显然有：

$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是一样的