程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> ZOJ 3527 Shinryaku! Kero Musume(樹DP)

ZOJ 3527 Shinryaku! Kero Musume(樹DP)

編輯:C++入門知識

ZOJ 3527 Shinryaku! Kero Musume(樹DP)


2300 years ago, Moriya Suwako was defeated by Yasaka Kanako in the Great Suwa War. As the goddess of mountains in Gensokyo, she was planning to make a comeback and regain faith among humans.

 

TH_KeroSuwako.jpg

 

To achieve her great plan, she decides to build shrines in human villages. Of course, each village can bulid at most one shrine. If she builds a shrine in the i-th village, she can get Fifaith points.

Because of geological differences and the Quantum Entanglement theory, each village has one and only one entangled village Pi (it is a kind of one-way relationship). If Suwakobuilds shrines both in the i-th village and the Pi-th village, the faith she get from the i-th village will changes by Gi points (it can result to a negative value of faith points). If she only builds a shrine in the Pi-th village, but not in the i-th village, the faith she get will not changes.

Now, please help Suwako to find out the maximal faith points she can get.

Input

There are multiple test cases. For each test case:

The first line contains an integer N (2 <= N <= 100000) indicates the number of villages in Gensokyo. Then followed by N lines, each line contains three integers Fi (0 <= Fi <= 100000) Gi (-100000 <= Gi <= 100000) Pi (1 <= Pi <= N and Pi will not point to the i-th village itself).

Output

For each test case, output the maximal faith points that Suwako can get.

Sample Input

2
3 -1 2
2 -2 1
4
3 -2 2
4 -3 3
2 -1 1
5 -2 2

Sample Output

3
9

題意:在N個村莊選建聖地,如果在僅在PI建,不會損失滿意度,如果在PI的兒子節點

也建會損失G滿意度,問你選建時的最大滿意度

分析:咋一看跟普通的樹DP沒啥區別,設dp[i][1]:為在第i個點建的最大滿意度,dp[i][0]

不在第i個點建的最大滿意度,但是存在環,我們來分析這個環的特點,每個村莊僅有一個entangled village

也就是說連邊(有向)的時候每個點僅有一個入邊,如果存在環的話,只有可能從環上的點開始向環外的點

邊,而且不會存在雙環。所以我們就在環上選定一點,分選與不選做兩次樹形DP,取最大值即可。

對於不在環上的點直接拓撲排序排除掉即可。

 

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
#define REPF( i , a , b ) for ( int i = a ; i <= b ; ++ i )
#define REP( i , n ) for ( int i = 0 ; i < n ; ++ i )
#define CLEAR( a , x ) memset ( a , x , sizeof a )
typedef long long LL;
const LL INF = (1LL<<50);
typedef pairpil;
const int maxn=1e5+100;
struct node{
    int to,next;
    int val;
}e[maxn];
int n,tot;
LL dp[maxn][2];
int head[maxn],in[maxn];
int vis[maxn],a[maxn];
void addedge(int u,int v,int w)
{
    e[tot].to=v;e[tot].next=head[u];
    e[tot].val=w;head[u]=tot++;
}
void dfs(int u,int fa)
{
    dp[u][0]=0;
    dp[u][1]=a[u];
    for(int i=head[u];i!=-1;i=e[i].next)
    {
        int to=e[i].to;
        if(to!=fa)
           dfs(to,fa);
        dp[u][0]+=max(dp[to][0],dp[to][1]);
        dp[u][1]+=max(dp[to][0],dp[to][1]+e[i].val);
    }
}
LL solve(int u)
{
    LL ans1=0,ans2=0;
    dp[u][0]=0;dp[u][1]=-INF;
    for(int i=head[u];i!=-1;i=e[i].next)
    {
        int v=e[i].to;
        dfs(v,u);
        ans1+=max(dp[v][0],dp[v][1]);
    }
    dp[u][0]=-INF;dp[u][1]=a[u];
    for(int i=head[u];i!=-1;i=e[i].next)
    {
        int v=e[i].to;
        dfs(v,u);
        ans2+=max(dp[v][0],dp[v][1]+e[i].val);
    }
    return max(ans1,ans2);
}
bool ok(int u,int fa)
{
    vis[u]=1;
    for(int i=head[u];i!=-1;i=e[i].next)
    {
        int to=e[i].to;
        if(to==fa)
            return true;
        if(ok(to,fa))
            return true;
    }
    return false;
}
void topsort()
{
    queueq;
    for(int i=1;i<=n;i++)
        if(!in[i]) q.push(i);
    while(!q.empty())
    {
        int x=q.front();
        q.pop();
        vis[x]=1;
        for(int i=head[x];i!=-1;i=e[i].next)
        {
            int to=e[i].to;
            in[to]--;
            if(!in[to])
               q.push(to);
        }
    }
}
int main()
{
    int x,y,w;
    while(~scanf(%d,&n))
    {
        CLEAR(head,-1);tot=0;
        CLEAR(vis,0);CLEAR(in,0);
        for(int i=1;i<=n;i++)
        {
            scanf(%d%d%d,&a[i],&w,&y);
            addedge(y,i,w);in[i]++;
        }
        topsort();
        LL ans=0;
        for(int i=1;i<=n;i++)
        {
           if(!vis[i]&&ok(i,i))
               ans+=solve(i);
        }
        printf(%lld
,ans);
    }
    return 0;
}

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved