fzu2157（树形dp）

http://acm.fzu.edu.cn/problem.php?pid=2157

这是一道很水的树形dp吧，本来不想写它的题解的，不过比赛的时候，队友说要我做这个题目，但是由于我感觉另一个题目可以出，而放弃做这个题目.....本来可以多出一道的，结果......以后的比赛中，还是得多多注意这个方面的问题。

题意：给出n个点，每个点都有两种花费，一个是0种花费，一个是1种花费，每两个点相连，边也有花费，是随着点所取话费的种类不同，边的花费也不同，边有四种花费，00，01，10，11 问建成整颗树所需要的最少花费。

思路：dp[i][0]代表当前结点取0种花费时建好以i结点为根节点的最少花费，dp[i][1]代表当前结点取1种花费时建好以i结点为根节点的最少花费，那么有动态转移方程就出来了.......

#include<iostream>

#include<cstdio>

#include<cstring>

#include<vector>

#include<algorithm>

using namespace std;

#define inf (1<<28)

struct node

{

    int k;

    int a,b,c,d;

};

int s[200005][2],dp[200005][2];

int t[200005][2][2],n;

vector<node>vet[200005];

void dfs(int root)

{

    if(vet[root].size()==0)

    {

        dp[root][0]=s[root][0];

        dp[root][1]=s[root][1];

        return;

    }

    dp[root][0]=s[root][0];

    dp[root][1]=s[root][1];

    for(int i=0;i<vet[root].size();i++)

    {

        node p=vet[root][i];

        dfs(p.k);

        dp[root][0]+=min(dp[p.k][0]+p.a,dp[p.k][1]+p.b);

        dp[root][1]+=min(dp[p.k][0]+p.c,dp[p.k][1]+p.d);

    }

}

int main()

{

    int text;

    scanf("%d",&text);

    while(text--)

    {

        scanf("%d",&n);

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

        scanf("%d",&s[i][0]);

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

        scanf("%d",&s[i][1]);

        for(int i=0;i<=n;i++)

        {

            vet[i].clear();

            dp[i][0]=dp[i][1]=0;

        }

        for(int i=0;i<n-1;i++)

        {

            int x,y,a,b,c,d;

            scanf("%d%d%d%d%d%d",&x,&y,&a,&b,&c,&d);

            node p;

            p.k=y;

            p.a=a;

            p.b=b;

            p.c=c;

            p.d=d;

            vet[x].push_back(p);

            //t[i][0][0]=a;

            //t[i][0][1]=b;

            //t[i][1][0]=c;

            //t[i][1][1]=d;

        }

        dfs(1);

        printf("%d\n",min(dp[1][0],dp[1][1]));

    }

    return 0;

}

巴特西

fzu2157（树形dp）

最新文章

热门文章