1 /* 2 題意：給一個DAG圖，n個節點，每個節點都對應一個值，入度為零的點走到出度為零的點，計算所有可能路徑 3 經過節點值的和最大！ 4 5 思路：記憶話搜索：也就是如果我們搜索到某一個節點的時候發現該節點已經存在了值，那么直接返回該節點的值！ 6 和回溯的思想差不多吧！ 7 8 注意：我們是正向建圖，并且記憶話搜索是先將子節點的最優值計算出來，然后在計算父節點的最優值 9 所以最終的最優值的結果在 入度為0的節點上！ 10 */ 11 #include<iostream> 12 #include<cstdio> 13 #include<cstring> 14 #include<algorithm> 15 #include<vector> 16 #define INF -0x3f3f3f3f 17 #define N 100005 18 using namespace std; 19 20 vector<int>g[N]; 21 int v[N], dp[N], vis[N]; 22 int n, m; 23 24 int dfs(int u){ 25 if(g[u].size()==0) 26 return dp[u]=v[u]; 27 if(dp[u]!=INF) return dp[u];//如果u節點已經根據其 子節點 計算過了，直接返回 28 int len=g[u].size(); 29 for(int i=0; i<len; ++i)//否則從它的子節點值 計算它的值！ 30 dp[u]=max(dp[u], dfs(g[u][i])+v[u]); 31 return dp[u]; 32 } 33 34 int main(){ 35 while(scanf("%d%d", &n, &m)!=EOF){ 36 for(int i=1; i<=n; ++i) 37 scanf("%d", &v[i]); 38 memset(vis, 0, sizeof(vis)); 39 for(int i=1; i<=n; ++i) 40 dp[i]=INF; 41 while(m--){ 42 int u, v; 43 scanf("%d%d", &u, &v); 44 g[u].push_back(v); 45 vis[v]=1; 46 } 47 for(int i=1; i<=n; ++i) 48 if(!vis[i]) 49 dfs(i); 50 51 int maxCost=INF; 52 for(int i=1; i<=n; ++i){ 53 if(!vis[i] && dp[i]>maxCost) 54 maxCost=dp[i]; 55 g[i].clear(); 56 } 57 printf("%d\n", maxCost); 58 } 59 return 0; 60 }
?
,怎么處理?)
)
的區別)
)
)
)
)
