WUST 1627 打怪游戏（优先队列+bfs）

灰太狼 2022-06-13 14:43 196阅读 0赞

## 1627: 打怪游戏 ##

Time Limit: 1 Sec Memory Limit: 128 MB 64bit IO Format: %lld  
Submitted: 12 Accepted: 10  
\[ [Submit][]\]\[ [Status][]\]\[ [Web Board][]\]

## Description ##

一颗树有n个节点（编号从0到n-1），树上每一个节点可能有多只怪物。 小明在0号节点，他想要清除这棵树上所有的怪物。

他现在有atk大小的攻击力。只有当他的攻击力大于怪物的防御力时，他才可以打败该怪物。每打败一只怪物，还会增加一定的攻击力。

一个节点可能存在着不止一只怪兽，你要打败这个节点的所有怪物才能可以从这个节点通过，

请问他能不能完成这个任务？

注意：不要求一次性杀光一个节点里面的所有怪物。

## Input ##

含多组测试数据。

每组测试数据的第1行包含两个整数n，m，分别表示这棵树有n个节点，m只怪兽(1<=n<=1000 ,0<=m <=100)

接下来的n-1行（即第2至n行），每行两个整数u，v，表示编号为u，v之间的节点有一条无向边，保证不会成环。（0<=u,v<n , u!=v)

接下来的1行包含一个整数atk，表示小明的初始化攻击力(0<=atk<=100)

接下来的m行，每行3个整数id，def，add\_atk，表示在编号为id的点上，有一只防御力为def的怪物，打败后可以增加add\_atk点的攻击力。(0<=add\_atk,def<=100)

## Output ##

对于每组测试样例，如果小明能够清除所有的怪物，则输出“Oh yes.” 否则，输出“Good Good Study,Day Day Up.”

## Sample Input ![copy.gif][] ##

5 2
    0 1
    0 2
    2 3
    2 4
    11
    3 10 2
    1 11 0

##                    ##

## Sample Output ##

Oh yes.

题解：

看起来好难的样子。。其实很水，数据也比较弱很好过，稍微搜了下思路就自己写了qwq，一遍ac，就是优先队列的运用和bfs，如果没怪就加一个增加攻击力和防御力都为0的假怪，不打怪也要好好学习天天向上

代码：

#include<iostream>
    #include<stdio.h>
    #include<string>
    #include<cstring>
    #include<map>
    #include<queue>
    #include<stack>
    #include<algorithm>
    #include<math.h>
    using namespace std;
    int p[1005][1005];
    struct node
    {
        int atk,def,be;//atk为增加的攻击力，def为防御力，be为怪物属于那个点
        friend bool operator<(const node& x,const node& y)//优先队列运算符重载，因为定义优先队列时默认是less<node>,所以要重载小于号
        {
            if(x.def!=y.def)
                return x.def<y.def;//防御低的在前
            else
                return x.atk>y.atk;//同防御增加攻击高的在前
        }
    };
    node mon[205];//保存怪物
    int num[105];//记录每一个节点的怪物数目
    int biao[1005][105];//记录每一个节点对应的怪物标号
    priority_queue<node>q;//定义优先队列
    int main()
    {
        int i,j,k,n,m,x,y,atk,tag;
        node now;
        while(scanf("%d%d",&n,&m)!=EOF)
        {
            while(!q.empty())q.pop();
            memset(p,0,sizeof(p));
            memset(num,0,sizeof(num));
            for(i=0;i<n-1;i++)
            {
                scanf("%d%d",&x,&y);//用邻接矩阵保存情况
                p[x][y]=1;
                p[y][x]=1;
            }
            scanf("%d",&atk);
            for(i=0;i<m;i++)//保存每个点怪物情况
            {
                scanf("%d%d%d",&mon[i].be,&mon[i].atk,&mon[i].def);
                biao[i][num[mon[i].be]]=i;
                num[mon[i].be]++;
            }
            for(i=0;i<n;i++)//为了能够走下去，把没怪的地方设置成怪防御和加的攻击力为0，num置为1
            {
                if(num[i]==0)
                {
                    now.atk=0;
                    now.be=i;
                    now.def=0;
                    mon[m]=now;
                    biao[i][0]=m;
                    m++;
                    num[i]++;
                }
            }
            for(i=0;i<num[0];i++)//出发位置放进队列进行bfs
            {
                now=mon[biao[0][i]];
                q.push(now);
            }
            tag=1;
            while(!q.empty())
            {
                now=q.top();
                q.pop();
                if(atk<=now.def)//如果男主遇到最小防御怪不能过就好好学习天天向上了qwq
                {
                    tag=0;
                    break;
                }
                else
                {
                    atk+=now.atk;
                    num[now.be]--;
                    if(num[now.be]==0)//没怪了
                    {
                        for(i=0;i<n;i++)//邻接矩阵查找通向的点
                        {
                            if(p[now.be][i])
                            {
                                for(j=0;j<num[i];j++)
                                {
                                    q.push(mon[biao[i][j]]);
                                }
                            }
                        }
                    }
                }
            }
            if(tag)
                printf("Oh yes.\n");
            else
                printf("Good Good Study,Day Day Up.\n");
        }
        return 0;
    }

[Submit]: http://acm.wust.edu.cn/submitpage.php?id=1627&soj=0
[Status]: http://acm.wust.edu.cn/problemstatus.php?id=1627&soj=0
[Web Board]: http://acm.wust.edu.cn/bbs.php?pid=1627&soj=0
[copy.gif]: http://acm.wust.edu.cn/image/copy.gif