题目传送门：https://www.luogu.com.cn/problem/P1073
思路：首先，我们目的是想要在图上dp求最优的路线，但是原图上会存在环，那么我们就要先通过tarjan缩点，将所有环缩成一个点，同时，记录每个点的最大值和最小值，缩点得到DAG后，我们可以在DAG上进行dp，每次转移有三种方式，一是保留上一个点的dp值，二是求得目前所在点的值，三是这个点本身的dp值，三者取最大就ok了。还要注意的是，在建DAG图的时候，要记录每个点的入度，在之后的dp过程中，每一个点在全部走到的时候，才能压入队列，进行更新操作，保证dp内的值是最优的，也就是无后效性。
代码：
1 #include2 #include 64 if (!dfn[i]) { 65 tarjan(i); 66 } 67 } 68 for (int u = 1; u ) { 69 for (int j = 0; j < G[u].size(); j++) { 70 int v = G[u][j]; 71 if (scc[u] != scc[v]) { 72 DAG[scc[u]].push_back(scc[v]); 73 in[scc[v]]++; 74 } 75 } 76 } 77 } 78 79 queue<int>q; 80 void dagdp(int s) { 81 82 q.push(s); 83 dp[s] = max(dp[s], Max[s] - Min[s]); 84 while (!q.empty()) { 85 86 int u = q.front(); 87 q.pop(); 88 for (int i = 0; i < DAG[u].size(); i++) { 89 int v = DAG[u][i]; 90 in[v]--; 91 Min[v] = min(Min[v], Min[u]); 92 dp[v] = max(dp[v], max(dp[u], Max[v] - Min[v])); 93 if (!in[v]) q.push(v); 94 } 95 96 } 97 98 } 99 100 void init() { 101 for (int i = 0; i 10; i++) G[i].clear(); 102 for (int i = 0; i 10; i++) DAG[i].clear(); 103 memset(dp, 0, sizeof(dp)); 104 memset(scc, 0, sizeof(scc)); 105 memset(ins, 0, sizeof(ins)); 106 memset(dfn, 0, sizeof(dfn)); 107 memset(low, 0, sizeof(low)); 108 dfncnt = 0, scccnt = 0; 109 memset(Min, 0x3f, sizeof(Min)); 110 } 111 112 int main() { 113 114 ios::sync_with_stdio(false); 115 cin.tie(0), cout.tie(0); 116 //int n, m; 117 cin >> n >> m; 118 init(); 119 for (int i = 1; i ) { 120 cin >> w[i]; 121 } 122 for (; m; --m) { 123 int u, v, c; 124 cin >> u >> v >> c; 125 G[u].push_back(v); 126 if (c == 2) G[v].push_back(u); 127 } 128 getdag(); 129 for (int i = 1; i ) { 130 Max[scc[i]] = max(Max[scc[i]], w[i]); 131 Min[scc[i]] = min(Min[scc[i]], w[i]); 132 } 133 dagdp(scc[1]); 134 cout << dp[scc[n]] << "\n"; 135 136 return 0; 137 }3 #include 4 #include 5 #include
永远热爱，永远向着光。
Original: https://www.cnblogs.com/wabi/p/16537313.html
Author: Kyrizer_W
Title: P1073 [NOIP2009 提高组] 最优贸易(tarjan缩点+dp)
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/587872/
转载文章受原作者版权保护。转载请注明原作者出处！