DAG图拓扑 + dp-白红宇

DAG图拓扑 + dp

阅读量：5167 次

发布时间：2019-06-13

本文共 2178 字，大约阅读时间需要 7 分钟。

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            using namespace std;int n, m, T;struct Node{ int to; int dis; Node(){} Node(int x, int y) { to = x; dis = y; }};const int maxn = 5050;const int INF = 0x3f3f3f3f;int indeg[maxn];queue
            
              q;vector
             
               g[maxn];int dp[maxn][maxn];int pre[maxn][maxn];void topsort(){ /* for(int i = 1; i <= n; i++) if(!indeg[i]) cout << i << " "; cout << endl; */ queue
              
                tmp; for(int i = 1; i <= n; i++) { if(indeg[i] == 0) { cout << "insert into tmp: " << i << endl; tmp.push(i); } } cout << "tmp seq is: " << endl; while(!tmp.empty()) { int u = tmp.front(); q.push(u); tmp.pop(); cout << u << " " ; cout << g[u].size() << " "; for(int i = 0; i < (int)g[u].size(); i++) { int t = g[u][i].to; indeg[t]--; if(!indeg[t]) tmp.push(t); } } cout << endl;}int main(){ int n; cin >> n >> m >> T; int a, b, c; for(int i = 0; i < m; i++) { cin >> a >> b >> c; g[a].push_back(Node(b, c)); //correct indeg[b]++; } //topsort(); //wrong queue
               
                 tmp; for(int i = 1; i <= n; i++) { if(indeg[i] == 0) { tmp.push(i); } } //cout << "tmp seq is: " << endl; while(!tmp.empty()) { int u = tmp.front(); q.push(u); tmp.pop(); //cout << u << " " ; for(int i = 0; i < (int)g[u].size(); i++) { int t = g[u][i].to; indeg[t]--; if(!indeg[t]) tmp.push(t); } } for(int i = 1; i <= n; i++) for(int j = 0; j < n; j++) dp[i][j] = INF;　　　　　　//dp[i][j]表示走到点i经过j个点（不包括终点i)的时间 dp[1][0] = 0; while(!q.empty()) { int now = q.front(); q.pop(); for(int i = 0; i < (int)g[now].size(); i++) { int to = g[now][i].to; int dis = g[now][i].dis; for(int j = 1; j < n; j++) // { if(dp[now][j - 1] + dis < dp[to][j]) { dp[to][j] = dp[now][j - 1] + dis; pre[to][j] = now; } } } } int max_num = 0; for(int i = 0; i < n; i++) { if(dp[n][i] <= T) { max_num = i; } } cout << max_num + 1<< endl; //因为dp表示的是经过的点，所以终点需+1 int num = max_num; int cur = n; stack
                
                  st; while(cur != 1)　　　　//存路径 { st.push(cur); cur = pre[cur][num]; num = num - 1; } cout << "1" << " ";　　 while(!st.empty()) { cout << st.top() << " "; st.pop(); } return 0;}