Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
欢迎参加IJCAI 2020麻将智能体竞赛,大奖等你拿!Welcome to IJCAI 2020 Mahjong AI competition with amazing prizes!

树形dp,拓扑排序遍历树

Posted by On18 at 2020-05-18 16:27:17 on Problem 2342
#include <iostream>
#include <queue>
#include <vector>
using namespace std;

int main()
{
    int n;
    while (cin >> n)
    {
        vector<int> rate(n + 1);
        vector<int> sup(n + 1);
        vector<int> in(n + 1);
        vector<vector<int>> dp(2, vector<int>(n + 1));
        for (int i = 1; i <= n; ++i)
            scanf("%d", &rate[i]);
        int a, b;
        while (scanf("%d %d", &a, &b) && a && b)
        {
            sup[a] = b;
            in[b] += 1;
        }
        queue<int> q;
        for (int i = 1; i <= n; ++i)
            if (in[i] == 0)
                q.push(i);
        int x;
        while (!q.empty())
        {
            x = q.front();
            q.pop();
            dp[1][x] += rate[x];
            int sx = sup[x];
            dp[1][sx] += max(dp[0][x], 0);
            dp[0][sx] += max(0, max(dp[1][x], dp[0][x]));
            in[sx] -= 1;
            if (in[sx] == 0 && sx > 0)
                q.push(sx);
        }
        cout << max(dp[0][x], dp[1][x]) << endl;
    }
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator