P1807 最长路_NOI导刊2010提高(07)

题目描述

设G为有n个顶点的有向无环图,G中各顶点的编号为1到n,且当为G中的一条边时有i < j。设w(i,j)为边的长度,请设计算法,计算图G中<1,n>间的最长路径。

输入格式

输入文件longest.in的第一行有两个整数n和m,表示有n个顶点和m条边,接下来m行中每行输入3个整数a,b,v(表示从a点到b点有条边,边的长度为v)。

输出格式

输出文件longest.out,一个整数,即1到n之间的最长路径.如果1到n之间没连通,输出-1。

输入输出样例

输入 #1

2 1

1 2 1

输出 #1

1

说明/提示

20%的数据,n≤100,m≤1000

40%的数据,n≤1,000,m≤10000

100%的数据,n≤1,500,m≤50000,最长路径不大于10^9

【思路】

拓扑排序 + DP

这道题和今天考试的第二题有点像

不过这道题必须要求的1到n这两个点之间的最长路

所以不能吧入度为0的点都放进去

而是应该只放进去1

对其他的入度为0但是不是1的点怎么处理呢?

枚举完1能到达的点并且减去入度之后

这些点不一定会为0

所以需要将那些多余的点删掉

这里的删掉指的是入度--

也就是把除了1以外的入度为0的点

进行拓扑排序

拓扑排序到的点就入度--

入度为0还是想像正常的拓扑一样放入栈/队列中去

直到栈/队列为空

然后再来一遍拓扑排序

只将1放入栈/队列中,

因为起点只能是1

在排序的过程中

可以进行DP

dp[i]表示i这个点到1的最长的距离

dp[i] = max(dp[i],dp[u] + w);

表示i这个点到1的最长距离等于max(它本身的值,他前一个点到1的最长距离+他和她前一个点之间的距离)

最后如果dp[n] == 0

也就是没有到达这个点

那就输出-1

否则输出dp[n]

【完整代码】

#include<iostream>
#include<cstdio>
#include<stack>
#define int long long
using namespace std;
const int Max = 50005;
struct node
{
int y,w,ne;
}a[Max];
int head[1505],sum = 0;
int into[1505];
void add(int u,int v,int w)
{
a[++ sum].y = v;
a[sum].ne = head[u];
a[sum].w = w;
head[u] = sum;
}
stack<int>s;
int dp[1505];
stack<int>q;
signed main()
{
int n,m;
cin >> n >> m;
int u,v,w;
for(register int i = 1;i <= m;++ i)
{
cin >> u >> v >> w;
add(u,v,w);
into[v] ++;
}
int jj = 0;
for(register int i = 1;i <= n;++ i)
if(into[i] == 0 && i != 1)
q.push(i);
while(!q.empty())
{
int u = q.top();
q.pop();
for(register int i = head[u];i != 0;i = a[i].ne)
{
into[a[i].y] --;
if(into[a[i].y] == 0)q.push(a[i].y);
}
}
s.push(1);
while(!s.empty())
{
int u = s.top();
s.pop();
for(register int i = head[u];i != 0;i = a[i].ne)
{
dp[a[i].y] = max(dp[a[i].y],dp[u] + a[i].w);
into[a[i].y] --;
if(into[a[i].y] == 0)s.push(a[i].y);
}
}
if(dp[n] == 0)cout << -1;
else cout << dp[n] << endl;
return 0;
}
05-28 22:40