首次架設靜態網站，如有疏失，還請多多包涵。歡迎來信zhuastor@gmail.com

解題心得

真正完全了解題目花了不少時間，覺得這題可以再多一些備註，我自己也在想像那個項目分布走了蠻多岔路的。然後基本上想對方向就不需要去管那個時限10s。

解題想法

直覺解法跟Topological排序有很大關係，事實也差不多，不過這題有些要注意的是，並不一定是”單一”個有向圖，而是可能有同時進行的”多”個有向圖，這點是解題的核心關鍵，除此之外沒其他太深的細節，所以我就開門見山地說了。
這題我的解法有兩個重點，dp陣列紀錄每個點在其所有指向該點的點中的最大花費時間，再整個N操作完後，透過mp、mp1的地圖連結性BFS所有有向圖，並對每個有向圖中所有點的dp取最大值，然後這些最大值再取一次最大值即為答案。
code有點複雜，個人建議把核心想懂後自己思考出解題路線再來參考程式碼。

AC code

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int m;
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin >> m;
    while(m--){
        int n,p,k;
        cin >> n;
        ll int dp[1005]={0};
        int a[1005];
        int r[1005]={0};
        bool ta[1005]={0};
        bool ta1[1005]={0};
        map<int,vector<int>>mp;
        map<int,vector<int>>mp1;
        ll int num=0;
        for(int x=1;x<=n;x++){
            cin >> a[x];
            cin >> k;
            for(int y=0;y<k;y++){
                cin >> p;
                mp[x].push_back(p);
                mp1[p].push_back(x);
                r[p]++;
            }
        }
	//Make dp[]
        queue<int>q;
        for(int x=1;x<=n;x++){
            if(r[x]==0 && !ta[x]){
                ll int maxd=0;
                q.push(x);
                while(!q.empty()){
                    int now=q.front();
                    q.pop();
                    ta[now]=true;
                    for(int x=0;x<mp[now].size();x++){
                        r[mp[now][x]]--;
                        dp[mp[now][x]]=max(dp[mp[now][x]],dp[now]+a[now]);
                        if(r[mp[now][x]]==0){
                            q.push(mp[now][x]);
                        }
                    }
                }
            }
        }
	//Start BFS all DAG and record max.
        for(int x=1;x<=n;x++){
            if(r[x]==0 && !ta1[x]){
                ll int maxd=0;
                q.push(x);
                while(!q.empty()){
                    int now=q.front();
                    q.pop();
                    if(ta1[now])continue;
                    ta1[now]=true;
                    maxd=max(maxd,dp[now]+a[now]);
                    for(int y=0;y<mp[now].size();y++){
                        if(!ta1[mp[now][y]]){
                            q.push(mp[now][y]);
                        }
                    }
                    for(int y=0;y<mp1[now].size();y++){
                        if(!ta1[mp1[now][y]]){
                            q.push(mp1[now][y]);
                        }
                    }
                }
                num=max(maxd,num);
            }
        }
        cout << num << endl;
    }

    return 0;
}

題目連結 : 2010年TOI研習營初選