[관건 경로] 프로젝트 (project)

프로젝트 (procject) 시간 제한: 1s 공간 제한: 256 M 제목 설명: 한 프로젝트 에 n 개의 작업 이 있 고 모든 작업 은 서로 다른 시간 이 필요 합 니 다.그 밖 에 일부 임무 간 에 제약 관계 가 있 는데 모든 임 무 를 시작 하려 면 반드시 어떤 임 무 를 먼저 완성 해 야 한 다 는 것 이다.예 를 들 어 차 를 우려 내기 전에 반드시 물 을 끓 여야 한다.만약 에 여러 개의 임 무 를 동시에 진행 할 수 있다 고 가정 하고 이 n 개의 임 무 를 완성 하 는 데 최소 얼마나 걸 리 는 지 물 어보 세 요.구속 관 계 는 링 이 나타 나 지 않 습 니 다. (즉, 퀘 스 트 A 를 시작 하려 면 퀘 스 트 B 를 먼저 완성 해 야 합 니 다. 퀘 스 트 B 를 시작 하려 면 퀘 스 트 C 를 먼저 완성 해 야 합 니 다. 퀘 스 트 C 를 시작 하려 면 퀘 스 트 A 를 먼저 완성 해 야 합 니 다. 링 이 나타 나 면 퀘 스 트 를 완성 할 수 없습니다.) 입력 형식: 첫 줄 두 개의 정수 n, m 는 n 개의 퀘 스 트 가 있 음 을 표시 합 니 다.m 개 구속 두 번 째 줄 n 개 정 수 는 각 퀘 스 트 를 완성 하 는 데 소요 되 는 시간 을 나타 내 고 다음 m 줄 마다 제약 a b 를 설명 하 며 퀘 스 트 b 를 시작 하려 면 반드시 퀘 스 트 a 출력 형식 을 완성 해 야 한다 고 표시 합 니 다. 출력 한 수 는 최소 시간 데이터 범위 와 약속 을 표시 합 니 다. 30% n < = 10, m < 2050% n < = 20, m < = 10070% n < = 1000, m < 2000 100% 1 < = n < = 10 ^ 5,m < = 10 ^ 5 샘플: input 6 610 5 7 4 61 32 43 64 6output 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("
");

19 //    for(int i=1;i<=n;i++)printf("%d ",next[i]);printf("
");

20 //  for(int i=1;i<=n;i++)printf("%d ",pre[i]);printf("
");

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 }