Bzoj3875 [Ahoi2014]骑士游戏

Time Limit: 30 Sec Memory Limit: 256 MB
Submit: 749 Solved: 392

Description

【故事背景】

长期的宅男生活中，JYY又挖掘出了一款RPG游戏。在这个游戏中JYY会

扮演一个英勇的骑士，用他手中的长剑去杀死入侵村庄的怪兽。

【问题描述】

在这个游戏中，JYY一共有两种攻击方式，一种是普通攻击，一种是法术攻

击。两种攻击方式都会消耗JYY一些体力。采用普通攻击进攻怪兽并不能把怪兽彻底杀死，怪兽的尸体可以变出其他一些新的怪兽，注意一个怪兽可能经过若干次普通攻击后变回一个或更多同样的怪兽；而采用法术攻击则可以彻底将一个怪兽杀死。当然了，一般来说，相比普通攻击，法术攻击会消耗更多的体力值（但由于游戏系统bug，并不保证这一点）。

游戏世界中一共有N种不同的怪兽，分别由1到N编号，现在1号怪兽入

侵村庄了，JYY想知道，最少花费多少体力值才能将所有村庄中的怪兽全部杀死呢？

Input

第一行包含一个整数N。

接下来N行，每行描述一个怪兽的信息；

其中第i行包含若干个整数，前三个整数为Si，Ki和Ri，表示对于i号怪兽，

普通攻击需要消耗Si的体力，法术攻击需要消耗Ki的体力，同时i号怪兽死亡后会产生Ri个新的怪兽。表示一个新出现的怪兽编号。同一编号的怪兽可以出现多个。

Output

输出一行一个整数，表示最少需要的体力值。

Sample Input

4
4 27 3 2 3 2
3 5 1 2
1 13 2 4 2
5 6 1 2

Sample Output

HINT

【样例说明】

首先用消耗4点体力用普通攻击，然后出现的怪兽编号是2，2和3。花费

10点体力用法术攻击杀死两个编号为2的怪兽。剩下3号怪兽花费1点体力进

行普通攻击。此时村庄里的怪兽编号是2和4。最后花费11点体力用法术攻击

将这两只怪兽彻底杀死。一共花费的体力是4+5+5+1+5+6=26。

【数据范围】

2<=N<=2*10^5,1<=Ri,Sigma(Ri)<=10^6,1<=Ki,Si<=5*10^14

Source

By 佚名上传

动态规划图论 SPFA

设f[i]为彻底干掉i的花费，可以列出DP方程 $ f[i]=min({s[i]+sum f[j] },f[i]) $

但这个状态是有后效性的，如果f[i]变了，所有关联到f[i]的状态都会变。

可以用类似SPFA的方式跑最短路，如果一个点被更新了，所有前驱点都入队重新决策。

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<cstring>
 4 #include<cstdio>
 5 #include<cmath>
 6 #include<vector>
 7 #include<queue>
 8 #define LL long long
 9 using namespace std;
10 const int mxn=300010;
11 LL read(){
12     LL x=0,f=1;char ch=getchar();
13     while(ch<'0' || ch>'9'){if(ch=='-')f=-1;ch=getchar();}
14     while(ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();}
15     return x*f;
16 }
17 struct edge{
18     int v,nxt;
19 }e[mxn<<2];
20 int hd[mxn],mct=0;
21 void add_edge(int u,int v){
22     e[++mct].v=v;e[mct].nxt=hd[u];hd[u]=mct;return;
23 }
24 vector<int>ve[mxn];
25 LL f[mxn],s[mxn];
26 bool inq[mxn];
27 int n,r;
28 void SPFA(){
29     queue<int>q;
30     for(int i=1;i<=n;i++){q.push(i);inq[i]=1;}
31     while(!q.empty()){
32         int u=q.front();q.pop();inq[u]=0;
33         LL tmp=s[u];
34         for(int i=hd[u];i;i=e[i].nxt)
35             tmp+=f[e[i].v];//普攻
36         if(tmp>=f[u])continue;
37         f[u]=tmp;
38         for(int i=0;i<ve[u].size();i++)
39             if(!inq[ve[u][i]]){
40                 inq[ve[u][i]]=1;
41                 q.push(ve[u][i]);
42             }
43     }
44     return;
45 }
46 int main(){
47     int i,j,w;
48     n=read();
49     for(i=1;i<=n;i++){
50         s[i]=read();f[i]=read();
51         w=read();
52         for(j=1;j<=w;j++){
53             r=read();
54             add_edge(i,r);
55             ve[r].push_back(i);//前驱 
56         }
57     }
58     SPFA();
59     printf("%lld
",f[1]);
60     return 0;
61 }