洛谷 P1807

本文主要是介绍洛谷 P1807，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

最长路

题目描述

设 $G$ 为有 $n$ 个顶点的带权有向无环图，$G$ 中各顶点的编号为 $1$ 到 $n$，请设计算法，计算图 $G$ 中 $1,n$ 间的最长路径。

输入格式

输入的第一行有两个整数，分别代表图的点数 $n$ 和边数 $m$。

第 $2$ 到第 $(m+1)$ 行，每行 $3$ 个整数 $u,v,w$（$u<v$），代表存在一条从 $u$ 到 $v$ 边权为 $w$ 的边。

输出格式

输出一行一个整数，代表 $1$ 到 $n$ 的最长路。

若 $1$ 无法到达 $n$，请输出 $-1$。

样例 #1

样例输入 #1

2 1
1 2 1

样例输出 #1

1

所以点 1 绝对是一个没有入度的点，而且不会出现环。而这一点正好满足拓扑的要求。但是，题目并不保证只有点1是没有入度的。所以要判断其他没有入度的点。而对他们的处理是？也许你一开始会想到加入队列，那你就错了！他们本身是无法到达的点，所以根本不可能会延伸到其他地方，如果加入队列，那么就会导致个别点，甚至所有点的答案错误。那么就是不管他？还是错了！如果不管，那么他们延伸出来的点的入度永远大于0，因为还有那些点。以至于发生和上一种方法一样的错误，甚至使终点无法到达！那么解决方法就是先做一遍 for 循环，找到那些点，再把延伸出来的点的入度 −1，如果这些点入度−1 后又变成了入度为 0 的点，那么再做同样的处理。

提示

【数据规模与约定】

• 对于 $20\%$的数据，$n\le 100$，$m\le 10^3$。
• 对于 $40\%$ 的数据，$n\le 10^3$，$m\le 10^4$。
• 对于 $100\%$ 的数据，$1\le n\le 1500$，$0\le m\le 5\times 10^4$，$1\le u,v\le n$，$-10^5\le w\le 10^5$。

#include <bits/stdc++.h>
using namespace std;
#define MAX 1505
vector<int> nextt[MAX],value[MAX];//记录邻接边以及对应权值 
long long len[MAX]; 
int in[MAX] = {0};
queue<int> q;//放入度为0的点 
int main()
{for(int i=0;i<MAX;i++) len[i] = -1e9;//初始化 放在下面的循环可以减少时间  len[1] = 0; //记得第一个点距离应该是0 int n,m;cin>>n>>m;for(int i=0;i<m;i++){int a,b,v;cin>>a>>b>>v;nextt[a].push_back(b);value[a].push_back(v);in[b]++;} //去除除了1之外其他入度为0的点的影响for(int i = 2;i<=n;i++){if(in[i] == 0){q.push(i);}} while(!q.empty()){int now = q.front();q.pop();for(int i=0;i<nextt[now].size();i++){
//			if(!--in[i]) q.push(i);  错啦！if(!--in[nextt[now][i]])  q.push(nextt[now][i]);}}q.push(1);while(!q.empty()){int now = q.front();q.pop();for(int i=0;i<nextt[now].size();i++){if(len[nextt[now][i]]<len[now]+value[now][i]) len[nextt[now][i]]=len[now]+value[now][i];if(!--in[nextt[now][i]]) q.push(nextt[now][i]);}}//for(int i=0;i<n;i++)//cout<<len[i]<<' ';//cout<<endl; if(len[n] == -1e9) cout<<"-1"<<endl;else cout<<len[n];return 0;
}

这篇关于洛谷 P1807的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---