POJ Test for Job(DAG上拓扑排序)

// #include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#define maxn 100005
#define maxm 1000005
#define ll long long
#define inf 0x3f3f3f3f3f3f3f3f
using namespace std;
struct Node{
  int to,next;
}Edge[maxm];
int head[maxn],num;
int n,m;
int depi[maxn], pre[maxn], depo[maxn];
ll dist[maxn];

void init(){
  for(int i=0;i<=n;i++){
    depi[i] = depo[i] = 0;
    head[i] = -1;
    dist[i] = -inf;
  }
  num = 0;
}

void add(int u,int v){
  Edge[num].to = v;
  Edge[num].next = head[u];
  head[u] = num ++;
}

void Topo(){
  queue<int> q;
  for(int i=1;i<=n;i++){
    if(depi[i] == 0){
      q.push(i);
      dist[i] = pre[i];
    }
  }
  while(!q.empty()){
    int u = q.front();
    q.pop();
    for(int i=head[u];i!=-1;i=Edge[i].next){
      int v = Edge[i].to;
      dist[v] = max(dist[v], dist[u] + pre[v]);
      if(--depi[v] == 0) q.push(v);
    }
  }
}

int main()
{
  while(~scanf("%d%d",&n,&m)){
    init();
    for(int i=1;i<=n;i++){
      scanf("%d",&pre[i]);
    }
    for(int i=0;i<m;i++){
      int u, v;
      scanf("%d%d",&u, &v);
      add(u, v);
      depi[v] ++;
      depo[u] ++;
    }
    Topo();
    ll ans = -inf;
    for(int i=1;i<=n;i++){
      if(depo[i] == 0) ans = max(ans, dist[i]);
    }
    printf("%lld\n", ans);
  }
  return 0;
}