1 /* 2 題意：n個(gè)任務(wù)，有某些任務(wù)要在一些任務(wù)之前完成才能開(kāi)始做！ 3 第k個(gè)任務(wù)的約束只能是1...k-1個(gè)任務(wù)！問(wèn)最終需要最少的時(shí)間完成全部的 4 任務(wù)！ 5 思路：第i個(gè)任務(wù)要在第j個(gè)任務(wù)之前做，就在i，j之間建立一條有向邊！ 6 如果第i個(gè)任務(wù)之前沒(méi)有任務(wù)，那么就是0和i建立一條有向邊！ 7 最后求一條0到所有節(jié)點(diǎn)距離的最大值！不一定是最后一個(gè)任務(wù)完成的 8 時(shí)間是最長(zhǎng)的時(shí)間....... 9 */ 10 #include<iostream> 11 #include<cstring> 12 #include<cstdio> 13 #include<algorithm> 14 #include<vector> 15 #include<queue> 16 #define N 10005 17 using namespace std; 18 19 struct Edge{ 20 int v, w; 21 Edge(){} 22 23 Edge(int v, int w){ 24 this->v=v; 25 this->w=w; 26 } 27 }; 28 29 queue<int>q; 30 vector<Edge>g[N]; 31 int d[N]; 32 int vis[N]; 33 int maxT; 34 void spfa(){ 35 q.push(0); 36 vis[0]=1; 37 while(!q.empty()){ 38 int u=q.front(); 39 q.pop(); 40 vis[u]=0; 41 int len=g[u].size(); 42 for(int i=0; i<len; ++i){ 43 int v=g[u][i].v, w=g[u][i].w; 44 if(d[v]<d[u]+w){ 45 d[v]=d[u]+w; 46 if(maxT<d[v]) maxT=d[v]; 47 if(!vis[v]){ 48 q.push(v); 49 vis[v]=1; 50 } 51 } 52 } 53 } 54 } 55 int main(){ 56 int n; 57 scanf("%d", &n); 58 for(int i=1; i<=n; ++i){ 59 d[i]=vis[i]=0; 60 int tt, m; 61 scanf("%d%d", &tt, &m); 62 if(m==0) g[0].push_back(Edge(i, tt)); 63 while(m--){ 64 int v; 65 scanf("%d", &v); 66 g[v].push_back(Edge(i, tt)); 67 } 68 } 69 maxT=0; 70 spfa(); 71 printf("%d\n", maxT); 72 return 0; 73 } 1 /* 2 思路：其實(shí)是一個(gè)簡(jiǎn)單的dp題目！ 3 */ 4 #include<iostream> 5 #include<cstring> 6 #include<cstdio> 7 #include<algorithm> 8 #define N 10005 9 using namespace std; 10 int dp[N]; 11 int main(){ 12 13 int n, maxT=0; 14 scanf("%d", &n); 15 for(int i=1; i<=n; ++i){ 16 int w, m; 17 scanf("%d%d", &w, &m); 18 if(m==0) dp[i]=w;//不僅僅只有1節(jié)點(diǎn)沒(méi)有約束節(jié)點(diǎn) 19 20 while(m--){ 21 int v; 22 scanf("%d", &v); 23 dp[i]=max(dp[i], dp[v]+w); 24 } 25 if(maxT<dp[i]) maxT=dp[i]; 26 } 27 printf("%d\n", maxT); 28 return 0; 29 }

?

轉(zhuǎn)載于:https://www.cnblogs.com/hujunzheng/p/3958867.html

總結(jié)

以上是生活随笔為你收集整理的poj1949Chores（建图或者dp）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。