算法
经典的差分约束系统呢
关于差分约束系统,我们可以将其归结为一类形如
y<=a[i]-a[j]<=x;
的方程组
然后单拎出来一边
a[i]-a[j]>=d;
移项a[i]>=a[j]+d;
是不是很像求最长路或者最短路的式子?
没错,我们就是要根据这些关系连一些边
通常情况下我们需要对要求答案的每相邻两项连边,具体边权要由题而定,
对于这道题的话就很好说了
对了,如果你就是喜欢最长或最短路的话,还可以乘-1变号哦~
#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define maxn 150017
int to[maxn<<2],nxt[maxn<<2],head[maxn<<2];
int val[maxn],dis[maxn];
int minn,maxx,cnt,n,m;
int vis[maxn];
void add(int u,int v,int w){
to[++cnt]=v;
nxt[cnt]=head[u];
head[u]=cnt;
val[cnt]=w;
}
int spfa(int s){
queue<int> q;
for(int i=minn;i<=maxx;i++) dis[i]=-inf;
dis[s]=0;q.push(s);vis[s]=1;
while(!q.empty()){
int u=q.front();q.pop();
vis[u]=0;
for(int i=head[u];i;i=nxt[i]){
int v=to[i];
if(dis[v]<dis[u]+val[i]){
dis[v]=dis[u]+val[i];
if(!vis[v]){
q.push(v);
vis[v]=1;
}
}
}
}
return dis[maxx];
}
int main(){
scanf("%d",&n);
minn=inf;
maxx=-1;
for(int i=1;i<=n;i++){
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
add(u-1,v,w);
maxx=max(v,maxx);
minn=min(u-1,minn);
}
for(int i=minn;i<=maxx;i++){
add(i,i+1,0);
add(i+1,i,-1);
}
int ans=spfa(minn);
printf("%d\n",ans);
return 0;
}