一眼定真，把约束转移到前缀和数组上。那么我们对于任意 到 之间要种 棵树的限制，转化为 。同时添加 和 的限制，跑差分约束即可。最劣复杂度 。
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n, m;
int dis[30005], vis[30005], inq[30005];
vector<int >vc[30005], w[30005];
void spfa() {
queue<int > q;
q.push(1);
dis[1] = 0;
vis[1] = 1;
while(!q.empty()) {
int p = q.front();
int v = dis[p];
q.pop();
inq[p] = 0;
for(int i = 0;i < vc[p].size();i ++)
if(v + w[p][i] < dis[vc[p][i]]) {
if(++vis[vc[p][i]] > n + 1) {
cout << "No";
exit(0);
}
if(!inq[vc[p][i]])
q.push(vc[p][i]), dis[vc[p][i]] = v + w[p][i], inq[vc[p][i]] = 1;
else
dis[vc[p][i]] = v + w[p][i];
}
}
}
signed main() {
memset(dis, 0x3f, sizeof dis);
cin >> n >> m;
for(int i = 1;i <= m;i ++) {
int t, u, v;
cin >> u >> v >> t;
u += 1;
v += 2;
vc[v].push_back(u);
w[v].push_back(-t);
}
for(int i = 3;i <= n + 2;i ++) {
vc[i - 1].push_back(i);
w[i - 1].push_back(1);
vc[i].push_back(i - 1);
w[i].push_back(0);
}
for(int i = 2;i <= n + 2;i ++) {
vc[1].push_back(i);
w[1].push_back(0);
}
spfa();
cout << dis[n + 2] - dis[2];
return 0;
}