BZOJ 3875: [Ahoi2014]骑士游戏

正文索引 [隐藏]

Input
Output
Sample Input
Sample Output
HINT
题解
代码

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

26

HINT

【样例说明】
首先用消耗4点体力用普通攻击，然后出现的怪兽编号是2，2和3。花费
10点体力用法术攻击杀死两个编号为2的怪兽。剩下3号怪兽花费1点体力进
行普通攻击。此时村庄里的怪兽编号是2和4。最后花费11点体力用法术攻击
将这两只怪兽彻底杀死。一共花费的体力是4+5+5+1+5+6=26。
【数据范围】
2<=N<=210^5,1<=Ri,Sigma(Ri)<=10^6,1<=Ki,Si<=510^14

题解

我勒个去、、我把暴力计算价值放在了SPFA寻找子节点的循环里【就是优先计算价值更新，然后已知TLE 80分、、、、】简直了、、、、
我们可以这么想，每一个怪兽都是由其他怪兽合成或者被魔法攻击制造的，这样，一开始所有怪兽的价值都是魔法攻击的体力，然后我们就像最短路一样不停地松弛每一条边，这样最后就能求得每个怪兽的最小消灭体力了。
说人话就是边反向，暴力计算价值，SPFA。

代码

/*Author:WNJXYK*/
#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
const int Maxn=200005;
const int Maxm=Maxn*5;
long long cost[Maxn];
int n;
struct Boss{
    long long mag,nor;
};
Boss boss[Maxn];
struct Link{
    int v;
    int nxt;
    long long num;
    Link(){
    }
    Link(int a,long long b,int c){
        v=a;
        num=b;
        nxt=c;
    }
};
Link l[Maxm];
int numel;
int link[Maxn];
inline void addLink(int u,int v,long long num){
    l[++numel]=Link(v,num,link[u]);
    link[u]=numel;
}
inline long long getCost(int u){
    long long Ans=0;
    for (int i=link[u];i;i=l[i].nxt){
        for (int j=1;j<=l[i].num;j++){
            Ans+=cost[l[i].v];
        }
    }
    return Ans;
}
struct Edge{
    int v;
    long long w;
    int nxt;
    Edge(){
    }
    Edge(int a,long long b,int c){
        v=a;w=b;nxt=c;
    }
};
Edge e[Maxm];
int nume;
int head[Maxn];
inline void addEdge(int u,int v,long long val){
    e[++nume]=Edge(v,val,head[u]);
    head[u]=nume;
}
queue<int> que;
bool inque[Maxn];
inline void spfa(){
    while(!que.empty())que.pop();
    for (int i=1;i<=n;i++) {
        que.push(i);
        inque[i]=true;
    }
    while(!que.empty()){
        int now=que.front();
        que.pop();inque[now]=false;
        long long nCost=getCost(now)+boss[now].nor;
        if (cost[now]>nCost){
            cost[now]=nCost;
            for (int i=head[now];i;i=e[i].nxt){
                if (inque[e[i].v]==false){
                    inque[e[i].v]=true;
                    que.push(e[i].v);
                }
            }
        }
    }
}
int lists;
int list[1000005];
int nums,num;
int main(){
    //freopen("knight.in","r",stdin);
    //freopen("knight.out","w",stdout);
    scanf("%d",&n);
    for (int i=1;i<=n;i++){
        scanf("%lld%lld",&boss[i].nor,&boss[i].mag);
        cost[i]=boss[i].mag;
        scanf("%d",&lists);
        if (lists==0) continue;
        for (int j=1;j<=lists;j++) scanf("%d",&list[j]);
        sort(list+1,list+lists+1);
        nums=1;num=list[1];
        for (int j=2;j<=lists;j++){
            if (list[j]==num){
                nums++;
            }else{
                addEdge(num,i,boss[i].nor);
                addLink(i,num,nums);
                num=list[j];
                nums=1;
            }
        }
        addEdge(num,i,boss[i].nor);
        addLink(i,num,nums);
    }
    spfa();
    printf("%lldn",cost[1]);
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

/*Author:WNJXYK*/

#include<cstdio>

#include<algorithm>

#include<queue>

using namespace std;

const int Maxn=200005;

const int Maxm=Maxn*5;

long long cost[Maxn];

int n;

struct Boss{

long long mag,nor;

};

Boss boss[Maxn];

struct Link{

int v;

int nxt;

long long num;

Link(){

}

Link(int a,long long b,int c){

v=a;

num=b;

nxt=c;

}

};

Link l[Maxm];

int numel;

int link[Maxn];

inline void addLink(int u,int v,long long num){

l[++numel]=Link(v,num,link[u]);

link[u]=numel;

}

inline long long getCost(int u){

long long Ans=0;

for (int i=link[u];i;i=l[i].nxt){

for (int j=1;j<=l[i].num;j++){

Ans+=cost[l[i].v];

}

return Ans;

}

struct Edge{

int v;

long long w;

int nxt;

Edge(){

}

Edge(int a,long long b,int c){

v=a;w=b;nxt=c;

}

};

Edge e[Maxm];

int nume;

int head[Maxn];

inline void addEdge(int u,int v,long long val){

e[++nume]=Edge(v,val,head[u]);

head[u]=nume;

}

queue<int> que;

bool inque[Maxn];

inline void spfa(){

while(!que.empty())que.pop();

for (int i=1;i<=n;i++) {

que.push(i);

inque[i]=true;

}

while(!que.empty()){

int now=que.front();

que.pop();inque[now]=false;

long long nCost=getCost(now)+boss[now].nor;

if (cost[now]>nCost){

cost[now]=nCost;

for (int i=head[now];i;i=e[i].nxt){

if (inque[e[i].v]==false){

inque[e[i].v]=true;

que.push(e[i].v);

}

int lists;

int list[1000005];

int nums,num;

int main(){

//freopen("knight.in","r",stdin);

//freopen("knight.out","w",stdout);

scanf("%d",&n);

for (int i=1;i<=n;i++){

scanf("%lld%lld",&boss[i].nor,&boss[i].mag);

cost[i]=boss[i].mag;

scanf("%d",&lists);

if (lists==0) continue;

for (int j=1;j<=lists;j++) scanf("%d",&list[j]);

sort(list+1,list+lists+1);

nums=1;num=list[1];

for (int j=2;j<=lists;j++){

if (list[j]==num){

nums++;

}else{

addEdge(num,i,boss[i].nor);

addLink(i,num,nums);

num=list[j];

nums=1;

}

addEdge(num,i,boss[i].nor);

addLink(i,num,nums);

}

spfa();

printf("%lldn",cost[1]);

return 0;

}

[fire]数据下载：链接：http://pan.baidu.com/s/1gdvi6jx 密码：c3la[/fire]

一	二	三	四	五	六	日
1	2	3	4	5	6	7
8	9	10	11	12	13	14
15	16	17	18	19	20	21
22	23	24	25	26	27	28
29	30	31

WNJXYKの博客

喂你脚下有坑