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();
vis[]=;
while(!q.empty()){
int u=q.front();
q.pop();
vis[u]=;
int len=g[u].size();
for(int i=; 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]=;
}
}
}
}
}
int main(){
int n;
scanf("%d", &n);
for(int i=; i<=n; ++i){
d[i]=vis[i]=;
int tt, m;
scanf("%d%d", &tt, &m);
if(m==) g[].push_back(Edge(i, tt));
while(m--){
int v;
scanf("%d", &v);
g[v].push_back(Edge(i, tt));
}
}
maxT=;
spfa();
printf("%d\n", maxT);
return ;
}
 /*
思路:其实是一个简单的dp题目!
*/
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#define N 10005
using namespace std;
int dp[N];
int main(){ int n, maxT=;
scanf("%d", &n);
for(int i=; i<=n; ++i){
int w, m;
scanf("%d%d", &w, &m);
if(m==) 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 ;
}
上一篇:Flex之自定义事件


下一篇:getParameter和getAttribute区别