给定一张带点权的DAG 求一条入度为0节点到出度为0节点的最长路
把点权转化为边权（同时多源转化成单源）：边u->v的权值为W[v]，这样入度为0的节点权值会被遗漏，新开一个点0向入度为0的点u连有向边，权值为W[u]，这样就只有0是入度为0的点了。
先进行拓扑排序，再求出最长路径（利用DAG分层的性质可以在线性时间内求出最长路）
1 #include2 #include 3 #include 4 #include 5 #include 6 using namespace std; 7 typedef long long LL; 8 9 template void read(T & x){10 register int c = getchar(), f = 1; x = 0;11 while(!isdigit(c)){ if (c == '-') f = -1; c = getchar();}12 while(isdigit(c)) x = x*10+(c&15), c = getchar();13 x *= f;14 }15 const int N = 100005;16 struct Edge{ int v, w, next;}G[N*20];17 int n, m, s, head[N], tot, ind[N], out[N], W[N]; LL dis[N], ans = -123023423423;18 void toposort(int s) {19 int topo[N], cnt = 0;20 topo[++cnt] = 0;21 for(int k = 0; k <= cnt; ++k)22 for(int i = head[topo[k]]; i; i = G[i].next) {23 int v = G[i].v;24 ind[v]--;25 if (ind[v]==0) topo[++cnt] = v;26 }27 memset(dis,0xc0,sizeof(dis));dis[s] = 0;28 for(int k = 0; k <= cnt; ++k)29 for(int i = head[topo[k]]; i; i = G[i].next) {30 int v = G[i].v, w = G[i].w;31 dis[v] = max(dis[topo[k]]+w, dis[v]);32 }33 }34 35 inline void add(int u, int v, int w) {36 G[++tot].v=v, G[tot].w=w, G[tot].next=head[u];head[u]=tot;37 ind[v]++, out[u]++;38 }39 40 int main(void){41 while(scanf("%d%d", &n, &m) == 2){42 memset(head,0,sizeof(head));tot=0;memset(ind,0,sizeof(ind));memset(out,0,sizeof(out));43 ans = 0xc0c0c0c0c0c0c0c0;44 for(int i = 1; i <= n; ++i) read(W[i]);45 for(int u, v, i = 1; i <= m; ++i) {46 read(u), read(v);47 add(u, v, W[v]);48 } 49 for(int i = 1; i <= n; ++i) {50 if (!ind[i]) add(0,i,W[i]);51 }52 toposort(s);53 for(int i = 1; i <= n; ++i) {54 if (!out[i]) ans = max(ans, dis[i]);55 }56 cout << ans << '\n';57 }58 return 0;59 }