首页 > 代码库 > 【模拟赛】工程(project)
【模拟赛】工程(project)
工程(project)
时间限制：1s
空间限制：256M
题目描述：
一项工程有n个任务，每个任务需要花费不同的时间。
除此之外，一些任务间还有约束关系，就是要开始每个任务必须先完成某些任务。
比如，要泡茶之前必须先烧水。
假设可以有任意多个任务同时进行，问完成这n个任务最少需要花费多少时间。
约束关系不会出现环（即不会出现要开始任务A必须先完成任务B，要开始任务B必须先完成任务C，要开始任务C又必须先完成任务A；如果出现了环的话就不能完成任务）
输入格式：
第一行两个正整数n，m表示有n个任务，m个约束
第二行n个整数表示完成每个任务需要消耗的时间
接下来m行每行描述一个约束
a b表示要开始任务b必须先完成任务a
输出格式：
输出一个数表示需要花费的最小时间
数据范围与约定：
30% n<=10,m<=20
50% n<=20,m<=100
70% n<=1000,m<=2000
100% 1<=n<=10^5,m<=10^5
样例：
input
6 6
10 5 7 8 4 6
1 3
2 3
2 4
3 5
3 6
4 6
output
23
求关键路径 然后 然后就没了
1 # include<cstdio> 2 # include<cstring> 3 const int maxn=100005; 4 int head,tail,n,m; 5 int pre[maxn],vis[maxn],v[maxn],fist[maxn],num[maxn],next[maxn],u[maxn],dis[maxn]; 6 void init(){ 7 memset(fist,-1,sizeof(fist)); 8 int e=1,a,b; 9 scanf("%d%d",&n,&m);10 for(int i=1;i<=n;i++)scanf("%d",&num[i]);11 for(int i=1;i<=m;i++){12 scanf("%d%d",&a,&b);13 pre[b]++;14 u[e]=a,v[e]=b;15 next[e]=fist[u[e]];16 fist[u[e]]=e++;17 }18 // for(int i=1;i<=n;i++)printf("%d ",fist[i]);printf("\n");19 // for(int i=1;i<=n;i++)printf("%d ",next[i]);printf("\n");20 // for(int i=1;i<=n;i++)printf("%d ",pre[i]);printf("\n");21 }22 void work(int id){23 if(num[id]>dis[id])dis[id]=num[id];24 for(int i=fist[id];i!=-1;i=next[i]){25 pre[v[i]]--;26 if(pre[v[i]]==0)vis[tail++]=v[i];27 if(dis[id]+num[v[i]]>dis[v[i]])28 dis[v[i]]=dis[id]+num[v[i]];29 }30 }31 void solve(){32 int t=0;33 for(int i=1;i<=n;i++)if(pre[i]==0)vis[t++]=i;//for(int i=0;i<t;i++)printf("%d ",vis[i]);34 head=0,tail=t;35 while(head<tail){36 work(vis[head]);37 head++;38 }39 40 }41 void print(){42 int max=-1;43 for(int i=1;i<=n;i++)44 if(dis[i]>max)max=dis[i];45 printf("%d",max);46 }47 int main(){48 freopen("project.in","r",stdin);49 freopen("project.out","w",stdout);50 init();51 solve();52 print();53 return 0;54 }
【模拟赛】工程(project)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。