题目链接:http://poj.org/problem?id=3249
————————————————————————————————————
题目大意: 有向图,点有点权,要求从入度为0点开始,以出度为0点作为终点,求一条权值最大的有向路径使经过点的点权和最大(可能存在负值)。
————————————————————————————————————
题目思路:拓扑排序 + dp
————————————————————————————————————
题目细节:
1、本题用到了vector ,可作为vector的一例参考、
2、由于没有加 v.clear() ,使得一开始超时了。(谢过某位同学!)
3、本题的dp部分可以用队列来做。
————————————————————————————————————
源代码:
#include<stdio.h> #include<stdlib.h> #include<vector> using namespace std; #define MAX 2147483647 vector<int> v[100010]; int in[100010]; int out[100010]; long long dp[100010]; int val[100010]; int vis[100010]; long long max(long long a, long long b) { if(a>b) return a; else return b; } int main() { int n = 0,m = 0; int i = 0,j = 0; int x = 0,y = 0; long long maxn = 0; int c = 0,t = 0; while(scanf("%d%d",&n,&m)!=EOF) { for(i = 1;i<=n;i++) { scanf("%d",&val[i]); in[i] = 0; out[i] = 0; vis[i] = 0; dp[i] = -MAX; v[i].clear(); } for(i = 0;i<m;i++) { scanf("%d%d",&x,&y); v[x].push_back(y); out[x]++; in[y]++; } for(i = 1;i<=n;i++) if(in[i] == 0) dp[i] = val[i]; c = 1; while(c<n) { for(i = 1;i<=n;i++) { if(!vis[i] && in[i] == 0) { c++; vis[i] = 1; for(j = 0;j<v[i].size();j++) { t = v[i][j]; dp[t] = max(dp[t],dp[i]+val[t]); in[t]--; } } } } maxn = -MAX; for(i = 1;i<=n;i++) { if(out[i] == 0 && dp[i]>maxn) maxn = dp[i]; } printf("%lld\n",maxn); } return 0; }