题解 P1113 【杂务】

BriMon · 2018-03-24 19:29:49 · 题解

模拟赛考了这题QAQ

用到了拓扑排序思想；

每一个工作可以开始的前提是它的前期工作必须全部完成；

所以， 只需要从它前期工作的时间中取max加上它的时间， 就可以转移到它；

细节都在代码里了；

#include <bits/stdc++.h>//懒...

using namespace std;

int n;
int dp[10010];
int rud[10010];//入度 
int v[100010];//价值
int ans;

vector <int> net[10010];

inline void Search(int cur)
{
    for(register int i = 0 ; i < net[cur].size() ; i ++)
    {
        int x = net[cur][i];
        rud[x]--;
        dp[x] = max(dp[x], dp[cur] + v[x]);//状态转移 
        ans = max(ans, dp[x]);
        if(rud[x] == 0)
        {
             Search(x);
        }
    }
}

int main()
{
    cin >> n;

    for(register int i = 1 ; i <= n ; i ++)
    {
        int x;
        cin >> x;
        scanf("%d", &v[i]);
        int y;
        while(scanf("%d", &y) != EOF)
        {
            if(y == 0) break;
            rud[x]++;
            net[y].push_back(x);干完y后可以开始x 
        }
    }

    dp[1] = v[1];//注意！！！ 

    Search(1);//从第一项开始拓扑； 

    cout<<ans;

    return 0;
}

竟然这题只有60行？（我不是压行选手（逃.