poj1949Chores（建图或者dp）

/*
        题意：n个任务，有某些任务要在一些任务之前完成才能开始做！
                    第k个任务的约束只能是1...k-1个任务！问最终需要最少的时间完成全部的
                    任务！
       思路：第i个任务要在第j个任务之前做，就在i，j之间建立一条有向边！
                   如果第i个任务之前没有任务，那么就是0和i建立一条有向边！
                   最后求一条0到所有节点距离的最大值！不一定是最后一个任务完成的
                   时间是最长的时间.......
*/
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<queue>
#define N 10005
using namespace std;

struct Edge{
    int v, w;
    Edge(){}

    Edge(int v, int w){
        this->v=v;
        this->w=w;
    }
}; 

queue<int>q;
vector<Edge>g[N];
int d[N];
int vis[N];
int maxT;
void spfa(){
    q.push(0);
    vis[0]=1;
    while(!q.empty()){
        int u=q.front();
        q.pop();
        vis[u]=0;
        int len=g[u].size();
        for(int i=0; i<len; ++i){
            int v=g[u][i].v, w=g[u][i].w;
            if(d[v]<d[u]+w){
                d[v]=d[u]+w;
                if(maxT<d[v]) maxT=d[v];
                if(!vis[v]){
                    q.push(v);
                    vis[v]=1;
                }
            }
        }
    }
}
int main(){
    int n;
    scanf("%d", &n);
    for(int i=1; i<=n; ++i){
            d[i]=vis[i]=0;
            int tt, m;
            scanf("%d%d", &tt, &m);
            if(m==0) g[0].push_back(Edge(i, tt));
            while(m--){
                int v;
                scanf("%d", &v);
                g[v].push_back(Edge(i, tt));
            }
    }
    maxT=0;
    spfa();
    printf("%d\n", maxT);
    return 0;
}

/*
          思路：其实是一个简单的dp题目！
*/
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#define N 10005
using namespace std;
int dp[N];
int main(){

    int n, maxT=0;
    scanf("%d", &n);
    for(int i=1; i<=n; ++i){
        int w, m;
        scanf("%d%d", &w, &m);
        if(m==0) dp[i]=w;//不仅仅只有1节点没有约束节点

        while(m--){
            int v;
            scanf("%d", &v);
            dp[i]=max(dp[i], dp[v]+w);
        }
        if(maxT<dp[i]) maxT=dp[i];
    }
    printf("%d\n", maxT);
    return 0;
}