题解 | #Magic Maze#

堪称最大连续字段和的图论版本 链接https://www.luogu.com.cn/problem/P1115

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e4 + 10;
vector<vector<pair<int, int>>>g;
int ans, in[N], f[N];
void solve()
{
	ans = 0;
	int n, m; cin >> n >> m;
	g.clear(); g.resize(n + 1);
	memset(f, 0, sizeof f);
	memset(in, 0, sizeof in);
	while(m --)
	{
		int u, v, w; cin >> u >> v >> w;
		g[u].push_back({v, w});
		in[v] ++;
    }
    
	queue<int>q;
	for(int i = 0; i < n; i ++) if(!in[i]) q.push(i);
	while(q.size())
	{
		int u = q.front();
		q.pop();
		for(auto i : g[u])
		{
			int v = i.first, w = i.second;
			in[v] --;
			f[v] = max(f[v], f[u] + w);
			ans = max(ans, f[v]);
			if(!in[v]) q.push(v);
		} 
	}
	cout << ans << '\n'; 
}
/*
1
3 2
0 1 -10
1 2 20
*/
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int t = 1; cin >> t;
	while(t --) solve(); 
}