louisfghbvc的部落格

題目連結:   https://onlinejudge.org/external/4/452.pdf

題目大意:  找出最大需要多久時間，才能完成所有工作。

思路:   這題WA很多次，我把每個排成總時間加起來了，其實是最大排程時間，因為時間平行。直接DFS。用入邊=0表示開始DFS的地方。

而且被輸入坑，輸入第一筆不一定都是起點。

DFS從最後點開始回溯，挑最長的那段加起來。

代碼:  

#include <bits/stdc++.h>
#define N 28
using namespace std;
int in[N], wt[N], sum[N];
int g[N][N];

void dfs(int u){
    int t = 0;
    for(int v = 0; v < 27; ++v) if(g[u][v]){
        dfs(v);
        t = max(sum[v], t);
    }
    sum[u] = t+wt[u];
}

int main()
{
    //freopen("out.txt", "w", stdout);
    int t;
    cin >> t;
    cin.ignore();
    cin.ignore();
    string s;
    while(t--){
        memset(in, 0, sizeof in);
        memset(wt, 0, sizeof wt);
        memset(g, 0, sizeof g);
        memset(sum, 0, sizeof sum);

        while(getline(cin, s)){
            if(s.empty()) break;
            stringstream ss(s);
            char v, u; int w;
            ss >> v >> w;
            wt[v-'A'] = w;
            while(ss >> u){
                g[u-'A'][v-'A'] = 1;
                in[v-'A']++;
            }
        }

        int mx = 0;
        for(int i = 0; i < 27; ++i) if(!in[i]){
            dfs(i);
            mx = max(sum[i], mx);
        }
        cout << mx << endl;
        if(t) puts("");
    }
}
/**
2

A 5
B 3 A
D 2 A
C 2 B
F 2 CE
E 4 DC

A 5
B 3 A
D 2 A
C 2 B
F 2 CE
E 4 DC

**/