题目链接:http://poj.org/problem?id=3249
题意是给了n个点,m条边(单向边),然后每个点都有一个点权(存在负权),问从入度为0的点开始到出度为0的点,最大的权值和为多少。
题目中说了这是一个DAG图(有向无环图),跑最长路的话会超时(spfa反向建边好像可以过),根据有向无环图的性质我们可以用拓扑排序来写,根据每条边的度数来选择边的顺序从而更新最长路的值。
AC代码:
// #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; }
本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。
我来说两句