Code 備忘錄►DP

TOJ::164 / 關鍵邏輯閘

http://2014.sprout.csie.org/oj/pro/164/
這題是DAG(有向無環圖)上的DP回朔。

題目要求所有路徑中最大的路徑上總共有幾個點。因為路徑可能一樣大，回朔會變成一張圖。
首先建圖，之後把入度是0的點丟到queue裡，以類似SPFA的方式鬆弛點連出去的點，把DP值更新，因為要回朔，假設A連到B，如果A點的DP值加上B點的權重會大於B點的DP值，就把B點的回朔邊清空，加上一條指向A點的邊。如果A點的DP值加上B點的權重會等於B點的DP值，則增加一條回朔邊指向A(不清空)。
做完順便將B點的入度減1，當入度為0時將該點丟到queue裡(已經沒有點會更新它了)。
如果一個點的出度為0，我就將他連到特殊點，方法跟上面一樣。
最後只要對特殊點的回朔圖(也是一張DAG)做DFS，計算點的數量，就可以得到答案了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include <cstdlib>
#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
#define N 100001
#define F(n) Fi(i,n)
#define Fi(i,n) Fl(i,0,n)
#define Fl(i,l,n) for(int i=l;i<n;i++)
using namespace std;
vector<int>D[N],B[N];
int T[N],TDP[N],IN[N];
bool wed[N];
int DFS(int now){
    wed[now]=true;
    int sum=1;
    F(B[now].size())if(!wed[B[now][i]])sum+=DFS(B[now][i]);
    return sum;
}
int main(int argc,char *argv[])
{
    ios_base::sync_with_stdio(false);
    int n,m,a,b;
    cin>>n>>m;
    F(n)cin>>TDP[i+1];
    F(m){
        cin>>a>>b;
        D[a].push_back(b);
        T[b]=TDP[b];
        IN[b]++;
    }
    queue<int>qq;
    F(n)if(IN[i+1]==0)qq.push(i+1);
    while(!qq.empty()){
        int now=qq.front();
        qq.pop();
        if(D[now].size()==0){
            if(TDP[now]>TDP[0]){
                TDP[0]=TDP[now];
                B[0].clear();
                B[0].push_back(now);
                //cout<<"DD "<<now<<endl;
            }else if(TDP[now]==TDP[0]){
                B[0].push_back(now);
                //cout<<"EE "<<now<<endl;
            }
            continue;
        }
        F(D[now].size()){
            if(TDP[now]+T[D[now][i]]>TDP[D[now][i]]){
                TDP[D[now][i]]=TDP[now]+T[D[now][i]];
                B[D[now][i]].clear();
                B[D[now][i]].push_back(now);
                //cout<<"DD "<<now<<' '<<D[now][i]<<endl;
            }else if(TDP[now]+T[D[now][i]]==TDP[D[now][i]]){
                B[D[now][i]].push_back(now);
                //cout<<"EE "<<now<<' '<<D[now][i]<<endl;
            }
            if(--IN[D[now][i]]==0){
                //cout<<"! "<<D[now][i]<<endl;
                qq.push(D[now][i]);
            }
        }
    }
    cout<<DFS(0)-1<<endl;
    //F(n)if(wed[i+1])cout<<i+1<<' ';cout<<endl;
    //F(n)cout<<TDP[i+1]<<' ';cout<<endl;
    //cin>>n;
    return 0;
}