首页 > 代码库 > P1113 杂务
P1113 杂务
P1113 杂务
题目描述
John的农场在给奶牛挤奶前有很多杂务要完成，每一项杂务都需要一定的时间来完成它。比如：他们要将奶牛集合起来，将他们赶进牛棚，为奶牛清洗乳房以及一些其它工作。尽早将所有杂务完成是必要的，因为这样才有更多时间挤出更多的牛奶。当然，有些杂务必须在另一些杂务完成的情况下才能进行。比如：只有将奶牛赶进牛棚才能开始为它清洗乳房，还有在未给奶牛清洗乳房之前不能挤奶。我们把这些工作称为完成本项工作的准备工作。至少有一项杂务不要求有准备工作，这个可以最早着手完成的工作，标记为杂务1。John有需要完成的n个杂务的清单，并且这份清单是有一定顺序的，杂务k(k>1)的准备工作只可能在杂务1..k-1中。
写一个程序从1到n读入每个杂务的工作说明。计算出所有杂务都被完成的最短时间。当然互相没有关系的杂务可以同时工作，并且，你可以假定John的农场有足够多的工人来同时完成任意多项任务。
输入输出格式
输入格式：
第1行：一个整数n，必须完成的杂务的数目(3<=n<=10,000)；
第2 ~ n+1行： 共有n行，每行有一些用1个空格隔开的整数，分别表示：
工作序号(1..n,在输入文件中是有序的)；
完成工作所需要的时间len（1<=len<=100）；
- 一些必须完成的准备工作，总数不超过100个，由一个数字0结束。有些杂务没有需要准备的工作只描述一个单独的0，整个输入文件中不会出现多余的空格。
输出格式：
一个整数，表示完成所有杂务所需的最短时间。
输入输出样例
输入样例#1：
71 5 02 2 1 03 3 2 04 6 1 05 1 2 4 06 8 2 4 07 4 3 5 6 0
输出样例#1：
23
思路：拓扑排序，求完成所有任务的最大时间。
在进入每一层时，求出到达这个点的最大时间。（因为要保证所有的任务都完成）
1 #include<iostream> 2 #include<cstdio> 3 #include<queue> 4 #include<algorithm> 5 6 using namespace std; 7 const int N = 10005; 8 9 queue <int> q;10 bool e[N][N];11 int ti[N];12 int mx[N];13 int ru[N];14 int n,ans;15 16 void topo()17 {18 for(int i=1;i<=n;++i)19 if(ru[i] == 0) 20 {21 q.push(i);22 mx[i] = ti[i];23 }24 while(!q.empty())25 {26 int d = q.front();27 q.pop();28 for(int i=1;i<=n;++i)29 {30 if(e[d][i])31 {32 ru[i]--;33 if(ru[i]==0) q.push(i);34 mx[i] = max(mx[i],mx[d]+ti[i]);35 }36 }37 }38 for(int i=1;i<=n;++i)39 ans = max(ans,mx[i]);40 }41 int main()42 {43 scanf("%d",&n);44 for(int i=1;i<=n;++i)45 {46 int a,b,c;47 scanf("%d%d%d",&a,&b,&c);48 ti[a] = b;49 while(c!=0)50 {51 ru[a]++;52 e[c][a] = true;53 scanf("%d",&c);54 }55 }56 topo();57 printf("%d",ans);58 return 0;59 }
P1113 杂务
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。