————————————————————————————————————
題目大意: 有向圖,點有點權,要求從入度為0點開始,以出度為0點作為終點,求一條權值最大的有向路徑使經過點的點權和最大(可能存在負值)。
————————————————————————————————————
題目思路:拓撲排序 + dp
————————————————————————————————————
題目細節:
1、本題用到瞭vector ,可作為vector的一例參考、
2、由於沒有加 v.clear() ,使得一開始超時瞭。(謝過某位同學!)
3、本題的dp部分可以用隊列來做。
————————————————————————————————————
源代碼:
[cpp]
#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]; www.aiwalls.com
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;
}
作者:violet_xrym