zzuli 1907: 小火山的宝藏收益邻接表+DFS

alan-W 2021-08-27 原文

邻接表+DFS

Time Limit: 1 Sec Memory Limit: 128 MB
Submit: 113 Solved: 24

Description

进去宝藏后，小火山发现宝藏有N个房间，且这n个房间通过N-1道门联通。

每一个房间都有一个价值为Ai的宝藏，但是每一个房间也都存在一个机关。如果小火山取走了这个房间的宝藏，那么这个房间通往其他房间的门就永远打不开了，也就是说后面的宝藏小火山是得不到了（进入这个房间的门是不会关闭的，小火山还是可以回去的）；如果小火山不取这个宝藏，而是去打开通往另一房间的门，那么这个房间的宝藏就会消失，小火山就得不到这个房间的宝藏。

不过，小火山已经有了藏宝图，知道每一个房间的宝藏的价值，现在想请你帮小火山算一下，他最多能获得多少钱去买股票？

Input

输入第一行是一个整数T（T <= 50), 表示一共有T组数据。

对于每一组数据，第一行是两个数N, S（1 <= N <= 10000, 1 <= S <= N), N代表有N个房间， S代表小火山进去宝藏后的

起始房间（小火山怎么进入起始房间不重要），第二行是N个数，代表每个房间宝藏的价值，随后N-1行，每行两个数A, B，代表

A, B这两个房间联通。

Output

对于每一组数据输出一个整数，代表小火山能获得的最大钱数。

Sample Input

2
1 1
20
3 1
4 5 6
1 2
2 3

Sample Output

20
6

题目思路：用邻接表存图，然后进行DFS，每次DFS只有两种选择：

1.取当前点的宝藏

2.放弃当前点的宝藏继续前行。

#include<cstdio>
#include<stdio.h>
#include<cstdlib>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<string>
#include<cstring>
#include<vector>
#include<queue>
#define INF 0x3f3f3f3f
#define MAX 100005

using namespace std;

struct node
{
    int u,v,w,next;
}Map[MAX];

int a[MAX],k,n,s,vis[MAX];

long long val[MAX];

void Add(int u,int v)
{
    Map[k].u=u;
    Map[k].v=v;
    Map[k].w=1;
    Map[k].next=a[u];
    a[u]=k++;
}

long long DFS(int u)
{
    int i,ok=0;
    long long sum=0;
    for(i=a[u];i!=-1;i=Map[i].next)
    {
        int v=Map[i].v;
        if(!vis[v])
        {
            ok=1;
            vis[v]=1;
            sum+=DFS(v);
            //vis[v]=0;
        }
    }
    if(!ok)
        return val[u];//如果u能到达的点都被标记过，只能去u点的宝藏
    return max(val[u],sum);//择优返回
}

int main()
{
    int T,i,u,v,w;
    scanf("%d",&T);
    while(T--)
    {
        k=1;
        for(i=0;i<MAX;i++)
            a[i]=-1;
        memset(vis,0,sizeof(vis));
        scanf("%d%d",&n,&s);
        for(i=1;i<=n;i++)
            scanf("%d",&val[i]);
        for(i=1;i<n;i++)
        {
            scanf("%d%d",&u,&v);
            Add(u,v);
            Add(v,u);
        }
        vis[s]=1;
        long long maxn=max(val[s],DFS(s));
        printf("%lld\n",maxn);
    }
    return 0;
}