【拓扑排序 离散化】P9981 [USACO23DEC] Minimum Longest Trip G|普及+

发布于：2025-06-01 ⋅ 阅读:(27) ⋅ 点赞:(0)

本文涉及知识点

C++图论 离散化

P9981 [USACO23DEC] Minimum Longest Trip G

题目描述

Bessie 正在奶牛大陆上旅行。奶牛大陆由从 1 1 1 到 N N N 编号的 N N N（ 2 ≤ N ≤ 2 ⋅ 10 5 2 \le N \le 2\cdot 10^5 2≤N≤2⋅105）座城市和 M M M（ 1 ≤ M ≤ 4 ⋅ 10 5 1 \le M \le 4\cdot 10^5 1≤M≤4⋅105）条单向道路组成。第 i i i 条路从城市 a i a_i ai​ 通向城市 b i b_i bi​，标签为 l i l_i li​。

由城市 x 0 x_0 x0​ 开始的长度为 k k k 的旅程被定义为一个城市序列 x 0 , x 1 , … , x k x_0,x_1,\ldots,x_k x0​,x1​,…,xk​，对于所有的 0 ≤ i < k 0 \le i < k 0≤i<k，存在由城市 x i x_i xi​ 到 x i + 1 x_{i+1} xi+1​ 的路。保证在奶牛大路上不存在长度无限的旅程，不存在两条路连接一对相同的城市。

对于每座城市，Bessie 想知道从它开始的最长旅程。对于一些城市，从它们开始的最长旅程不唯一，Bessie 将选择其中道路标签序列字典序更小的旅程。一个序列比等长的另一个序列字典序更小，当且仅当在它们不同的第一个位置，前者比后者的元素更小。

输出 Bessie 在每座城市选择的旅途的长度和道路标签之和。

输入格式

第一行包含 N N N 和 M M M。

接下来 M M M 行，每行三个整数 a i , b i , l i a_i,b_i,l_i ai​,bi​,li​，代表一条由 a i a_i ai​ 到 b i b_i bi​，标签为 l i l_i li​ 的单向道路。

输出格式

输出 N N N 行，第 i i i 行包含由空格分隔的两个整数，表示 Bessie 选择的从城市 i i i 开始的旅程的长度和道路标签之和。

输入输出样例 #1

输入 #1

4 5
4 3 10
4 2 10
3 1 10
2 1 10
4 1 10

输出 #1

0 0
1 10
1 10
2 20

输入输出样例 #2

输入 #2

4 5
4 3 4
4 2 2
3 1 5
2 1 10
4 1 1

输出 #2

0 0
1 10
1 5
2 12

输入输出样例 #3

输入 #3

4 5
4 3 2
4 2 2
3 1 5
2 1 10
4 1 1

输出 #3

0 0
1 10
1 5
2 7

输入输出样例 #4

输入 #4

4 5
4 3 2
4 2 2
3 1 10
2 1 5
4 1 1

输出 #4

0 0
1 5
1 10
2 7

说明/提示

样例解释 2

在下面的解释中，我们用 a i → l i b i a_i\xrightarrow{l_i} b_i ai​li​ ​bi​ 表示由城市 a i a_i ai​ 通往 b i b_i bi​，标签为 l i l_i li​ 的单向道路。

从城市 4 4 4 出发有多条旅程，包含 4 → 4 3 → 5 1 4\xrightarrow{4} 3\xrightarrow 5 1 44 ​35 ​1， 4 → 1 1 4\xrightarrow 1 1 41 ​1 和 4 → 2 2 → 10 1 4\xrightarrow 2 2\xrightarrow{10} 1 42 ​210 ​1。在这些旅程中， 4 → 4 3 → 5 1 4\xrightarrow{4} 3\xrightarrow 5 1 44 ​35 ​1 和 4 → 2 2 → 10 1 4\xrightarrow 2 2\xrightarrow{10} 1 42 ​210 ​1 是最长的。它们的长度均为 2 2 2，道路标签序列分别为 [ 4 , 5 ] [4,5] [4,5] 和 [ 2 , 10 ] [2,10] [2,10]。 [ 2 , 10 ] [2,10] [2,10] 是字典序更小的那一个，它的和为 12 12 12。

测试点性质

  • 测试点 5 − 6 5-6 5−6 满足所有道路的标签相同。
  • 测试点 7 − 8 7-8 7−8 满足所有道路的标签不相同。
  • 测试点 9 − 10 9-10 9−10 满足 N , M ≤ 5000 N,M \le 5000 N,M≤5000。
  • 测试点 11 − 20 11-20 11−20 没有额外限制。

拓扑排序

路径相同，取标签字典序小的。如果标签相等，则取任意路径，结果都一样。
如果没有叶子节点，长度为0，标签和也为0。
如果有子节点，取长度最大的节点。如果有多个长度最大的字节点，取字典序最小的。如果记录整个序列，那复杂度是O(n)，总复杂度：O(nn)，超过时间限制。
解决方案：
叶子节点是0层，其它节点的层次= 1 + max(子节点的层次)。
我们不需要记录整理个序列，只需要记录同层次各节点的顺序。
sort[i] = (i到j的标签)*108+sort[j] ，j是i的子节点。处理完一层后，对此层节点离散化。这样可以确保 sort[j] < N。
每个节点包括三个信息{最大长度，对应序列和，sort}
分三大步：
一，利用拓扑排序，求各节点层次leve。
二，求个层次包括哪些节点leveNodes。
三，从第0层开始处理。
a，更新结果。
b,离散化。

代码

核心代码

#include <iostream>
#include <sstream>
#include <vector>
#include<map>
#include<unordered_map>
#include<set>
#include<unordered_set>
#include<string>
#include<algorithm>
#include<functional>
#include<queue>
#include <stack>
#include<iomanip>
#include<numeric>
#include <math.h>
#include <climits>
#include<assert.h>
#include<cstring>
#include<list>

#include <bitset>
using namespace std;

template<class T1, class T2>
std::istream& operator >> (std::istream& in, pair<T1, T2>& pr) {
	in >> pr.first >> pr.second;
	return in;
}

template<class T1, class T2, class T3 >
std::istream& operator >> (std::istream& in, tuple<T1, T2, T3>& t) {
	in >> get<0>(t) >> get<1>(t) >> get<2>(t);
	return in;
}

template<class T1, class T2, class T3, class T4 >
std::istream& operator >> (std::istream& in, tuple<T1, T2, T3, T4>& t) {
	in >> get<0>(t) >> get<1>(t) >> get<2>(t) >> get<3>(t);
	return in;
}

template<class T = int>
vector<T> Read() {
	int n;
	cin >> n;
	vector<T> ret(n);
	for (int i = 0; i < n; i++) {
		cin >> ret[i];
	}
	return ret;
}
template<class T = int>
vector<T> ReadNotNum() {
	vector<T> ret;
	T tmp;
	while (cin >> tmp) {
		ret.emplace_back(tmp);
		if ('\n' == cin.get()) { break; }
	}
	return ret;
}

template<class T = int>
vector<T> Read(int n) {
	vector<T> ret(n);
	for (int i = 0; i < n; i++) {
		cin >> ret[i];
	}
	return ret;
}

template<int N = 1'000'000>
class COutBuff
{
public:
	COutBuff() {
		m_p = puffer;
	}
	template<class T>
	void write(T x) {
		int num[28], sp = 0;
		if (x < 0)
			*m_p++ = '-', x = -x;

		if (!x)
			*m_p++ = 48;

		while (x)
			num[++sp] = x % 10, x /= 10;

		while (sp)
			*m_p++ = num[sp--] + 48;
		AuotToFile();
	}
	void writestr(const char* sz) {
		strcpy(m_p, sz);
		m_p += strlen(sz);
		AuotToFile();
	}
	inline void write(char ch)
	{
		*m_p++ = ch;
		AuotToFile();
	}
	inline void ToFile() {
		fwrite(puffer, 1, m_p - puffer, stdout);
		m_p = puffer;
	}
	~COutBuff() {
		ToFile();
	}
private:
	inline void AuotToFile() {
		if (m_p - puffer > N - 100) {
			ToFile();
		}
	}
	char  puffer[N], * m_p;
};

template<int N = 1'000'000>
class CInBuff
{
public:
	inline CInBuff() {}
	inline CInBuff<N>& operator>>(char& ch) {
		FileToBuf();
		ch = *S++;
		return *this;
	}
	inline CInBuff<N>& operator>>(int& val) {
		FileToBuf();
		int x(0), f(0);
		while (!isdigit(*S))
			f |= (*S++ == '-');
		while (isdigit(*S))
			x = (x << 1) + (x << 3) + (*S++ ^ 48);
		val = f ? -x : x; S++;//忽略空格换行		
		return *this;
	}
	inline CInBuff& operator>>(long long& val) {
		FileToBuf();
		long long x(0); int f(0);
		while (!isdigit(*S))
			f |= (*S++ == '-');
		while (isdigit(*S))
			x = (x << 1) + (x << 3) + (*S++ ^ 48);
		val = f ? -x : x; S++;//忽略空格换行
		return *this;
	}
	template<class T1, class T2>
	inline CInBuff& operator>>(pair<T1, T2>& val) {
		*this >> val.first >> val.second;
		return *this;
	}
	template<class T1, class T2, class T3>
	inline CInBuff& operator>>(tuple<T1, T2, T3>& val) {
		*this >> get<0>(val) >> get<1>(val) >> get<2>(val);
		return *this;
	}
	template<class T1, class T2, class T3, class T4>
	inline CInBuff& operator>>(tuple<T1, T2, T3, T4>& val) {
		*this >> get<0>(val) >> get<1>(val) >> get<2>(val) >> get<3>(val);
		return *this;
	}
	template<class T = int>
	inline CInBuff& operator>>(vector<T>& val) {
		int n;
		*this >> n;
		val.resize(n);
		for (int i = 0; i < n; i++) {
			*this >> val[i];
		}
		return *this;
	}
	template<class T = int>
	vector<T> Read(int n) {
		vector<T> ret(n);
		for (int i = 0; i < n; i++) {
			*this >> ret[i];
		}
		return ret;
	}
	template<class T = int>
	vector<T> Read() {
		vector<T> ret;
		*this >> ret;
		return ret;
	}
private:
	inline void FileToBuf() {
		const int canRead = m_iWritePos - (S - buffer);
		if (canRead >= 100) { return; }
		if (m_bFinish) { return; }
		for (int i = 0; i < canRead; i++)
		{
			buffer[i] = S[i];//memcpy出错			
		}
		m_iWritePos = canRead;
		buffer[m_iWritePos] = 0;
		S = buffer;
		int readCnt = fread(buffer + m_iWritePos, 1, N - m_iWritePos, stdin);
		if (readCnt <= 0) { m_bFinish = true; return; }
		m_iWritePos += readCnt;
		buffer[m_iWritePos] = 0;
		S = buffer;
	}
	int m_iWritePos = 0; bool m_bFinish = false;
	char buffer[N + 10], * S = buffer;
};


class KMP
{
public:
	virtual int Find(const string& s, const string& t)
	{
		CalLen(t);
		for (int i1 = 0, j = 0; i1 < s.length(); )
		{
			for (; (j < t.length()) && (i1 + j < s.length()) && (s[i1 + j] == t[j]); j++);
			//i2 = i1 + j 此时s[i1,i2)和t[0,j)相等 s[i2]和t[j]不存在或相等
			//t[0,j)的结尾索引是j-1，所以最长公共前缀为m_vLen[j-1]，简写为y 则t[0,y)等于t[j-y,j)等于s[i2-y,i2)
			if (0 == j)
			{
				i1++;
				continue;
			}
			const int i2 = i1 + j;
			j = m_vLen[j - 1];
			i1 = i2 - j;//i2不变
		}
		return -1;
	}
	//vector<int> m_vSameLen;//m_vSame[i]记录 s[i...]和t[0...]最长公共前缀，增加可调试性 部分m_vSameLen[i]会缺失
	//static vector<int> Next(const string& s)
	//{// j = vNext[i] 表示s[0,i]的最大公共前后缀是s[0,j]
	//	const int len = s.length();
	//	vector<int> vNext(len, -1);
	//	for (int i = 1; i < len; i++)
	//	{
	//		int next = vNext[i - 1];
	//		while ((-1 != next) && (s[next + 1] != s[i]))
	//		{
	//			next = vNext[next];
	//		}
	//		vNext[i] = next + (s[next + 1] == s[i]);
	//	}
	//	return vNext;
	//}

	const vector<int> CalLen(const string& str)
	{
		m_vLen.resize(str.length());
		for (int i = 1; i < str.length(); i++)
		{
			int next = m_vLen[i - 1];
			while (str[next] != str[i])
			{
				if (0 == next)
				{
					break;
				}
				next = m_vLen[next - 1];
			}
			m_vLen[i] = next + (str[next] == str[i]);
		}
		return m_vLen;
	}
protected:
	int m_c;
	vector<int> m_vLen;//m_vLen[i] 表示str[0,i]的最长公共前后缀的长度
};

class CUnionFind
{
public:
	CUnionFind(int iSize) :m_vNodeToRegion(iSize)
	{
		for (int i = 0; i < iSize; i++)
		{
			m_vNodeToRegion[i] = i;
		}
		m_iConnetRegionCount = iSize;
	}
	CUnionFind(vector<vector<int>>& vNeiBo) :CUnionFind(vNeiBo.size())
	{
		for (int i = 0; i < vNeiBo.size(); i++) {
			for (const auto& n : vNeiBo[i]) {
				Union(i, n);
			}
		}
	}
	int GetConnectRegionIndex(int iNode)
	{
		int& iConnectNO = m_vNodeToRegion[iNode];
		if (iNode == iConnectNO)
		{
			return iNode;
		}
		return iConnectNO = GetConnectRegionIndex(iConnectNO);
	}
	void Union(int iNode1, int iNode2)
	{
		const int iConnectNO1 = GetConnectRegionIndex(iNode1);
		const int iConnectNO2 = GetConnectRegionIndex(iNode2);
		if (iConnectNO1 == iConnectNO2)
		{
			return;
		}
		m_iConnetRegionCount--;
		if (iConnectNO1 > iConnectNO2)
		{
			UnionConnect(iConnectNO1, iConnectNO2);
		}
		else
		{
			UnionConnect(iConnectNO2, iConnectNO1);
		}
	}

	bool IsConnect(int iNode1, int iNode2)
	{
		return GetConnectRegionIndex(iNode1) == GetConnectRegionIndex(iNode2);
	}
	int GetConnetRegionCount()const
	{
		return m_iConnetRegionCount;
	}
	vector<int> GetNodeCountOfRegion()//各联通区域的节点数量
	{
		const int iNodeSize = m_vNodeToRegion.size();
		vector<int> vRet(iNodeSize);
		for (int i = 0; i < iNodeSize; i++)
		{
			vRet[GetConnectRegionIndex(i)]++;
		}
		return vRet;
	}
	std::unordered_map<int, vector<int>> GetNodeOfRegion()
	{
		std::unordered_map<int, vector<int>> ret;
		const int iNodeSize = m_vNodeToRegion.size();
		for (int i = 0; i < iNodeSize; i++)
		{
			ret[GetConnectRegionIndex(i)].emplace_back(i);
		}
		return ret;
	}
private:
	void UnionConnect(int iFrom, int iTo)
	{
		m_vNodeToRegion[iFrom] = iTo;
	}
	vector<int> m_vNodeToRegion;//各点所在联通区域的索引,本联通区域任意一点的索引，为了增加可理解性，用最小索引
	int m_iConnetRegionCount;
};



class CNeiBo
{
public:
	static vector<vector<int>> Two(int n, const vector<pair<int, int>>& edges, bool bDirect, int iBase = 0)
	{
		vector<vector<int>>  vNeiBo(n);
		for (const auto& [i1, i2] : edges)
		{
			vNeiBo[i1 - iBase].emplace_back(i2 - iBase);
			if (!bDirect)
			{
				vNeiBo[i2 - iBase].emplace_back(i1 - iBase);
			}
		}
		return vNeiBo;
	}
	static vector<vector<int>> Two(int n, const vector<vector<int>>& edges, bool bDirect, int iBase = 0)
	{
		vector<vector<int>>  vNeiBo(n);
		for (const auto& v : edges)
		{
			vNeiBo[v[0] - iBase].emplace_back(v[1] - iBase);
			if (!bDirect)
			{
				vNeiBo[v[1] - iBase].emplace_back(v[0] - iBase);
			}
		}
		return vNeiBo;
	}
	static vector<vector<std::pair<int, int>>> Three(int n, vector<vector<int>>& edges, bool bDirect, int iBase = 0)
	{
		vector<vector<std::pair<int, int>>> vNeiBo(n);
		for (const auto& v : edges)
		{
			vNeiBo[v[0] - iBase].emplace_back(v[1] - iBase, v[2]);
			if (!bDirect)
			{
				vNeiBo[v[1] - iBase].emplace_back(v[0] - iBase, v[2]);
			}
		}
		return vNeiBo;
	}
	static vector<vector<int>> Mat(vector<vector<int>>& neiBoMat)
	{
		vector<vector<int>> neiBo(neiBoMat.size());
		for (int i = 0; i < neiBoMat.size(); i++)
		{
			for (int j = i + 1; j < neiBoMat.size(); j++)
			{
				if (neiBoMat[i][j])
				{
					neiBo[i].emplace_back(j);
					neiBo[j].emplace_back(i);
				}
			}
		}
		return neiBo;
	}
};



class CDGTopSort
{
public:
	template <class T = vector<int> >
	CDGTopSort(const vector<T>& vNeiBo) :m_vDeg(vNeiBo.size()) {
		const int N = vNeiBo.size();
		m_backNeiBo.resize(N);
		for (int cur = 0; cur < N; cur++)
		{
			m_vDeg[cur] = vNeiBo[cur].size();
			for (const auto& next : vNeiBo[cur])
			{
				m_backNeiBo[next].emplace_back(cur);
			}
		}
	}
	void Init() {

		auto Add = [&](int i) {
			if (0 != m_vDeg[i]) { return; }
			m_que.emplace(i);
		};
		for (int i = 0; i < m_vDeg.size(); i++)
		{
			Add(i);
		}
		while (m_que.size())
		{
			const int cur = m_que.front(); m_que.pop();
			if (!OnDo(cur)) { continue; }
			for (const auto& next : m_backNeiBo[cur])
			{
				m_vDeg[next]--;
				Add(next);
			}
		};
	}
	queue<int> m_que;
	vector<int> m_vDeg;
protected:
	vector<vector<int>> m_backNeiBo;
	virtual bool OnDo(int cur) { return true; };
};

template<class T = int>
class CDiscretize //离散化
{
public:
	CDiscretize(vector<T> nums)
	{
		sort(nums.begin(), nums.end());
		nums.erase(std::unique(nums.begin(), nums.end()), nums.end());
		m_nums = nums;
		for (int i = 0; i < nums.size(); i++)
		{
			m_mValueToIndex[nums[i]] = i;
		}
	}
	int operator[](const T value)const
	{
		auto it = m_mValueToIndex.find(value);
		if (m_mValueToIndex.end() == it)
		{
			return -1;
		}
		return it->second;
	}
	int size()const
	{
		return m_mValueToIndex.size();
	}
	vector<T> m_nums;
protected:
	unordered_map<T, int> m_mValueToIndex;
};

class CMyTopSort : public CDGTopSort
{
public:
	CMyTopSort(const vector<vector<int>>& vNeiBo) : CDGTopSort(vNeiBo), m_vNeiBo(vNeiBo) {
		m_leve.resize(vNeiBo.size());
	}
	vector<int> m_leve;
protected:
	virtual bool OnDo(int cur) {
		for (const auto& child : m_vNeiBo[cur]) {
			m_leve[cur] = max(m_leve[cur], m_leve[child] + 1);
		}
		return true;
	};
	const vector<vector<int>>& m_vNeiBo;
};
class Solution {
public:
	vector<pair<int, long long>> Ans(const int N, vector<tuple<int, int, int>>& edge) {
		vector<vector<int>> vNeiBo(N);
		vector<vector<pair<int, int>>> vNeiBo2(N);
		for (auto [u, v, w] : edge) {
			u--, v--;
			vNeiBo[u].emplace_back(v);
			vNeiBo2[u].emplace_back(v, w);
		}

		CMyTopSort topSort(vNeiBo);
		topSort.Init();
		int iMaxLeve = *max_element(topSort.m_leve.begin(), topSort.m_leve.end());
		vector<vector<int>> leveNodes(iMaxLeve + 1);
		for (int i = 0; i < topSort.m_leve.size(); i++) {
			leveNodes[topSort.m_leve[i]].emplace_back(i);
		}
		vector<tuple<int, long long, long long>> ans(N);
		for (const auto& v : leveNodes) {
			for (const auto& cur : v) {
				for (const auto& [child, w] : vNeiBo2[cur]) {
					tuple<int, long long, long long> cdata(1 + get<0>(ans[child]), -((long long)1e8 * w + get<1>(ans[child])), w + get<2>(ans[child]));
					if (cdata > ans[cur]) { ans[cur] = cdata; }
				}
				get<1>(ans[cur]) *= -1;
			}
			{
				vector<long long> tmp(v.size());
				for (int i = 0; i < v.size(); i++) {
					tmp[i] = get<1>(ans[v[i]]);
				}
				CDiscretize dis(tmp);
				for (int i = 0; i < v.size(); i++) {
					get<1>(ans[v[i]]) = dis[get<1>(ans[v[i]])];
				}
			}
		}
		vector<pair<int, long long>> ans2;
		for (const auto& [i1, i2, i3] : ans) {
			ans2.emplace_back(i1, i3);
		}
		return ans2;
	}
};

int main() {
#ifdef _DEBUG
	freopen("a.in", "r", stdin);
#endif // DEBUG	
	ios::sync_with_stdio(0);
	int n;
	cin >> n  ;
	auto edge = Read<tuple<int, int,int>>();
#ifdef _DEBUG		
	printf("N=%d", n);
	Out(edge, ",edge=");
	//Out(que, ",que=");
	/*Out(que, "que=");*/
#endif // DEBUG	
	auto res = Solution().Ans(n, edge);
	for (const auto& i : res)
	{
		cout << i.first << " " << i.second<< "\n";
	}
	return 0;
}

单元测试

#include <iostream>
#include <sstream>
#include <vector>
#include<map>
#include<unordered_map>
#include<set>
#include<unordered_set>
#include<string>
#include<algorithm>
#include<functional>
#include<queue>
#include <stack>
#include<iomanip>
#include<numeric>
#include <math.h>
#include <climits>
#include<assert.h>
#include<cstring>
#include<list>

#include <bitset>
using namespace std;

template<class T1, class T2>
std::istream& operator >> (std::istream& in, pair<T1, T2>& pr) {
	in >> pr.first >> pr.second;
	return in;
}

template<class T1, class T2, class T3 >
std::istream& operator >> (std::istream& in, tuple<T1, T2, T3>& t) {
	in >> get<0>(t) >> get<1>(t) >> get<2>(t);
	return in;
}

template<class T1, class T2, class T3, class T4 >
std::istream& operator >> (std::istream& in, tuple<T1, T2, T3, T4>& t) {
	in >> get<0>(t) >> get<1>(t) >> get<2>(t) >> get<3>(t);
	return in;
}

template<class T = int>
vector<T> Read() {
	int n;
	cin >> n;
	vector<T> ret(n);
	for (int i = 0; i < n; i++) {
		cin >> ret[i];
	}
	return ret;
}
template<class T = int>
vector<T> ReadNotNum() {
	vector<T> ret;
	T tmp;
	while (cin >> tmp) {
		ret.emplace_back(tmp);
		if ('\n' == cin.get()) { break; }
	}
	return ret;
}

template<class T = int>
vector<T> Read(int n) {
	vector<T> ret(n);
	for (int i = 0; i < n; i++) {
		cin >> ret[i];
	}
	return ret;
}

template<int N = 1'000'000>
class COutBuff
{
public:
	COutBuff() {
		m_p = puffer;
	}
	template<class T>
	void write(T x) {
		int num[28], sp = 0;
		if (x < 0)
			*m_p++ = '-', x = -x;

		if (!x)
			*m_p++ = 48;

		while (x)
			num[++sp] = x % 10, x /= 10;

		while (sp)
			*m_p++ = num[sp--] + 48;
		AuotToFile();
	}
	void writestr(const char* sz) {
		strcpy(m_p, sz);
		m_p += strlen(sz);
		AuotToFile();
	}
	inline void write(char ch)
	{
		*m_p++ = ch;
		AuotToFile();
	}
	inline void ToFile() {
		fwrite(puffer, 1, m_p - puffer, stdout);
		m_p = puffer;
	}
	~COutBuff() {
		ToFile();
	}
private:
	inline void AuotToFile() {
		if (m_p - puffer > N - 100) {
			ToFile();
		}
	}
	char  puffer[N], * m_p;
};

template<int N = 1'000'000>
class CInBuff
{
public:
	inline CInBuff() {}
	inline CInBuff<N>& operator>>(char& ch) {
		FileToBuf();
		ch = *S++;
		return *this;
	}
	inline CInBuff<N>& operator>>(int& val) {
		FileToBuf();
		int x(0), f(0);
		while (!isdigit(*S))
			f |= (*S++ == '-');
		while (isdigit(*S))
			x = (x << 1) + (x << 3) + (*S++ ^ 48);
		val = f ? -x : x; S++;//忽略空格换行		
		return *this;
	}
	inline CInBuff& operator>>(long long& val) {
		FileToBuf();
		long long x(0); int f(0);
		while (!isdigit(*S))
			f |= (*S++ == '-');
		while (isdigit(*S))
			x = (x << 1) + (x << 3) + (*S++ ^ 48);
		val = f ? -x : x; S++;//忽略空格换行
		return *this;
	}
	template<class T1, class T2>
	inline CInBuff& operator>>(pair<T1, T2>& val) {
		*this >> val.first >> val.second;
		return *this;
	}
	template<class T1, class T2, class T3>
	inline CInBuff& operator>>(tuple<T1, T2, T3>& val) {
		*this >> get<0>(val) >> get<1>(val) >> get<2>(val);
		return *this;
	}
	template<class T1, class T2, class T3, class T4>
	inline CInBuff& operator>>(tuple<T1, T2, T3, T4>& val) {
		*this >> get<0>(val) >> get<1>(val) >> get<2>(val) >> get<3>(val);
		return *this;
	}
	template<class T = int>
	inline CInBuff& operator>>(vector<T>& val) {
		int n;
		*this >> n;
		val.resize(n);
		for (int i = 0; i < n; i++) {
			*this >> val[i];
		}
		return *this;
	}
	template<class T = int>
	vector<T> Read(int n) {
		vector<T> ret(n);
		for (int i = 0; i < n; i++) {
			*this >> ret[i];
		}
		return ret;
	}
	template<class T = int>
	vector<T> Read() {
		vector<T> ret;
		*this >> ret;
		return ret;
	}
private:
	inline void FileToBuf() {
		const int canRead = m_iWritePos - (S - buffer);
		if (canRead >= 100) { return; }
		if (m_bFinish) { return; }
		for (int i = 0; i < canRead; i++)
		{
			buffer[i] = S[i];//memcpy出错			
		}
		m_iWritePos = canRead;
		buffer[m_iWritePos] = 0;
		S = buffer;
		int readCnt = fread(buffer + m_iWritePos, 1, N - m_iWritePos, stdin);
		if (readCnt <= 0) { m_bFinish = true; return; }
		m_iWritePos += readCnt;
		buffer[m_iWritePos] = 0;
		S = buffer;
	}
	int m_iWritePos = 0; bool m_bFinish = false;
	char buffer[N + 10], * S = buffer;
};


class KMP
{
public:
	virtual int Find(const string& s, const string& t)
	{
		CalLen(t);
		for (int i1 = 0, j = 0; i1 < s.length(); )
		{
			for (; (j < t.length()) && (i1 + j < s.length()) && (s[i1 + j] == t[j]); j++);
			//i2 = i1 + j 此时s[i1,i2)和t[0,j)相等 s[i2]和t[j]不存在或相等
			//t[0,j)的结尾索引是j-1，所以最长公共前缀为m_vLen[j-1]，简写为y 则t[0,y)等于t[j-y,j)等于s[i2-y,i2)
			if (0 == j)
			{
				i1++;
				continue;
			}
			const int i2 = i1 + j;
			j = m_vLen[j - 1];
			i1 = i2 - j;//i2不变
		}
		return -1;
	}
	//vector<int> m_vSameLen;//m_vSame[i]记录 s[i...]和t[0...]最长公共前缀，增加可调试性 部分m_vSameLen[i]会缺失
	//static vector<int> Next(const string& s)
	//{// j = vNext[i] 表示s[0,i]的最大公共前后缀是s[0,j]
	//	const int len = s.length();
	//	vector<int> vNext(len, -1);
	//	for (int i = 1; i < len; i++)
	//	{
	//		int next = vNext[i - 1];
	//		while ((-1 != next) && (s[next + 1] != s[i]))
	//		{
	//			next = vNext[next];
	//		}
	//		vNext[i] = next + (s[next + 1] == s[i]);
	//	}
	//	return vNext;
	//}

	const vector<int> CalLen(const string& str)
	{
		m_vLen.resize(str.length());
		for (int i = 1; i < str.length(); i++)
		{
			int next = m_vLen[i - 1];
			while (str[next] != str[i])
			{
				if (0 == next)
				{
					break;
				}
				next = m_vLen[next - 1];
			}
			m_vLen[i] = next + (str[next] == str[i]);
		}
		return m_vLen;
	}
protected:
	int m_c;
	vector<int> m_vLen;//m_vLen[i] 表示str[0,i]的最长公共前后缀的长度
};

class CUnionFind
{
public:
	CUnionFind(int iSize) :m_vNodeToRegion(iSize)
	{
		for (int i = 0; i < iSize; i++)
		{
			m_vNodeToRegion[i] = i;
		}
		m_iConnetRegionCount = iSize;
	}
	CUnionFind(vector<vector<int>>& vNeiBo) :CUnionFind(vNeiBo.size())
	{
		for (int i = 0; i < vNeiBo.size(); i++) {
			for (const auto& n : vNeiBo[i]) {
				Union(i, n);
			}
		}
	}
	int GetConnectRegionIndex(int iNode)
	{
		int& iConnectNO = m_vNodeToRegion[iNode];
		if (iNode == iConnectNO)
		{
			return iNode;
		}
		return iConnectNO = GetConnectRegionIndex(iConnectNO);
	}
	void Union(int iNode1, int iNode2)
	{
		const int iConnectNO1 = GetConnectRegionIndex(iNode1);
		const int iConnectNO2 = GetConnectRegionIndex(iNode2);
		if (iConnectNO1 == iConnectNO2)
		{
			return;
		}
		m_iConnetRegionCount--;
		if (iConnectNO1 > iConnectNO2)
		{
			UnionConnect(iConnectNO1, iConnectNO2);
		}
		else
		{
			UnionConnect(iConnectNO2, iConnectNO1);
		}
	}

	bool IsConnect(int iNode1, int iNode2)
	{
		return GetConnectRegionIndex(iNode1) == GetConnectRegionIndex(iNode2);
	}
	int GetConnetRegionCount()const
	{
		return m_iConnetRegionCount;
	}
	vector<int> GetNodeCountOfRegion()//各联通区域的节点数量
	{
		const int iNodeSize = m_vNodeToRegion.size();
		vector<int> vRet(iNodeSize);
		for (int i = 0; i < iNodeSize; i++)
		{
			vRet[GetConnectRegionIndex(i)]++;
		}
		return vRet;
	}
	std::unordered_map<int, vector<int>> GetNodeOfRegion()
	{
		std::unordered_map<int, vector<int>> ret;
		const int iNodeSize = m_vNodeToRegion.size();
		for (int i = 0; i < iNodeSize; i++)
		{
			ret[GetConnectRegionIndex(i)].emplace_back(i);
		}
		return ret;
	}
private:
	void UnionConnect(int iFrom, int iTo)
	{
		m_vNodeToRegion[iFrom] = iTo;
	}
	vector<int> m_vNodeToRegion;//各点所在联通区域的索引,本联通区域任意一点的索引，为了增加可理解性，用最小索引
	int m_iConnetRegionCount;
};



class CNeiBo
{
public:
	static vector<vector<int>> Two(int n, const vector<pair<int, int>>& edges, bool bDirect, int iBase = 0)
	{
		vector<vector<int>>  vNeiBo(n);
		for (const auto& [i1, i2] : edges)
		{
			vNeiBo[i1 - iBase].emplace_back(i2 - iBase);
			if (!bDirect)
			{
				vNeiBo[i2 - iBase].emplace_back(i1 - iBase);
			}
		}
		return vNeiBo;
	}
	static vector<vector<int>> Two(int n, const vector<vector<int>>& edges, bool bDirect, int iBase = 0)
	{
		vector<vector<int>>  vNeiBo(n);
		for (const auto& v : edges)
		{
			vNeiBo[v[0] - iBase].emplace_back(v[1] - iBase);
			if (!bDirect)
			{
				vNeiBo[v[1] - iBase].emplace_back(v[0] - iBase);
			}
		}
		return vNeiBo;
	}
	static vector<vector<std::pair<int, int>>> Three(int n, vector<vector<int>>& edges, bool bDirect, int iBase = 0)
	{
		vector<vector<std::pair<int, int>>> vNeiBo(n);
		for (const auto& v : edges)
		{
			vNeiBo[v[0] - iBase].emplace_back(v[1] - iBase, v[2]);
			if (!bDirect)
			{
				vNeiBo[v[1] - iBase].emplace_back(v[0] - iBase, v[2]);
			}
		}
		return vNeiBo;
	}
	static vector<vector<int>> Mat(vector<vector<int>>& neiBoMat)
	{
		vector<vector<int>> neiBo(neiBoMat.size());
		for (int i = 0; i < neiBoMat.size(); i++)
		{
			for (int j = i + 1; j < neiBoMat.size(); j++)
			{
				if (neiBoMat[i][j])
				{
					neiBo[i].emplace_back(j);
					neiBo[j].emplace_back(i);
				}
			}
		}
		return neiBo;
	}
};



class CDGTopSort
{
public:
	template <class T = vector<int> >
	CDGTopSort(const vector<T>& vNeiBo) :m_vDeg(vNeiBo.size()) {
		const int N = vNeiBo.size();
		m_backNeiBo.resize(N);
		for (int cur = 0; cur < N; cur++)
		{
			m_vDeg[cur] = vNeiBo[cur].size();
			for (const auto& next : vNeiBo[cur])
			{
				m_backNeiBo[next].emplace_back(cur);
			}
		}
	}
	void Init() {

		auto Add = [&](int i) {
			if (0 != m_vDeg[i]) { return; }
			m_que.emplace(i);
		};
		for (int i = 0; i < m_vDeg.size(); i++)
		{
			Add(i);
		}
		while (m_que.size())
		{
			const int cur = m_que.front(); m_que.pop();
			if (!OnDo(cur)) { continue; }
			for (const auto& next : m_backNeiBo[cur])
			{
				m_vDeg[next]--;
				Add(next);
			}
		};
	}
	queue<int> m_que;
	vector<int> m_vDeg;
protected:
	vector<vector<int>> m_backNeiBo;
	virtual bool OnDo(int cur) { return true; };
};

template<class T = int>
class CDiscretize //离散化
{
public:
	CDiscretize(vector<T> nums)
	{
		sort(nums.begin(), nums.end());
		nums.erase(std::unique(nums.begin(), nums.end()), nums.end());
		m_nums = nums;
		for (int i = 0; i < nums.size(); i++)
		{
			m_mValueToIndex[nums[i]] = i;
		}
	}
	int operator[](const T value)const
	{
		auto it = m_mValueToIndex.find(value);
		if (m_mValueToIndex.end() == it)
		{
			return -1;
		}
		return it->second;
	}
	int size()const
	{
		return m_mValueToIndex.size();
	}
	vector<T> m_nums;
protected:
	unordered_map<T, int> m_mValueToIndex;
};

class CMyTopSort : public CDGTopSort
{
public:
	CMyTopSort(const vector<vector<int>>& vNeiBo) : CDGTopSort(vNeiBo), m_vNeiBo(vNeiBo) {
		m_leve.resize(vNeiBo.size());
	}
	vector<int> m_leve;
protected:
	virtual bool OnDo(int cur) {
		for (const auto& child : m_vNeiBo[cur]) {
			m_leve[cur] = max(m_leve[cur], m_leve[child] + 1);
		}
		return true;
	};
	const vector<vector<int>>& m_vNeiBo;
};
class Solution {
public:
	vector<pair<int, long long>> Ans(const int N, vector<tuple<int, int, int>>& edge) {
		vector<vector<int>> vNeiBo(N);
		vector<vector<pair<int, int>>> vNeiBo2(N);
		for (auto [u, v, w] : edge) {
			u--, v--;
			vNeiBo[u].emplace_back(v);
			vNeiBo2[u].emplace_back(v, w);
		}

		CMyTopSort topSort(vNeiBo);
		topSort.Init();
		int iMaxLeve = *max_element(topSort.m_leve.begin(), topSort.m_leve.end());
		vector<vector<int>> leveNodes(iMaxLeve + 1);
		for (int i = 0; i < topSort.m_leve.size(); i++) {
			leveNodes[topSort.m_leve[i]].emplace_back(i);
		}
		vector<tuple<int, long long, long long>> ans(N);
		for (const auto& v : leveNodes) {
			for (const auto& cur : v) {
				for (const auto& [child, w] : vNeiBo2[cur]) {
					tuple<int, long long, long long> cdata(1 + get<0>(ans[child]), -((long long)1e8 * w + get<1>(ans[child])), w + get<2>(ans[child]));
					if (cdata > ans[cur]) { ans[cur] = cdata; }
				}
				get<1>(ans[cur]) *= -1;
			}
			{
				vector<long long> tmp(v.size());
				for (int i = 0; i < v.size(); i++) {
					tmp[i] = get<1>(ans[v[i]]);
				}
				CDiscretize dis(tmp);
				for (int i = 0; i < v.size(); i++) {
					get<1>(ans[v[i]]) = dis[get<1>(ans[v[i]])];
				}
			}
		}
		vector<pair<int, long long>> ans2;
		for (const auto& [i1, i2, i3] : ans) {
			ans2.emplace_back(i1, i3);
		}
		return ans2;
	}
};

int main() {
#ifdef _DEBUG
	freopen("a.in", "r", stdin);
#endif // DEBUG	
	ios::sync_with_stdio(0);
	int n;
	cin >> n  ;
	auto edge = Read<tuple<int, int,int>>();
#ifdef _DEBUG		
	printf("N=%d", n);
	Out(edge, ",edge=");
	//Out(que, ",que=");
	/*Out(que, "que=");*/
#endif // DEBUG	
	auto res = Solution().Ans(n, edge);
	for (const auto& i : res)
	{
		cout << i.first << " " << i.second<< "\n";
	}
	return 0;
}

扩展阅读

我想对大家说的话
工作中遇到的问题，可以按类别查阅鄙人的算法文章，请点击《算法与数据汇总》。
学习算法：按章节学习《喜缺全书算法册》，大量的题目和测试用例，打包下载。重视操作
有效学习：明确的目标 及时的反馈 拉伸区（难度合适） 专注
闻缺陷则喜(喜缺)是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛
失败+反思=成功 成功+反思=成功

视频课程

先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

测试环境

操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布