[题解/模板]POJ_1201（差分约束

差分约束不用判负环

设$s[i]$为0~i中选了几个数

根据题意$s[bi]-s[ai-1]>=ci$，

根据实际意义每个点最多选一个数$s[i+1]-s[i]>=0,s[i+1]-s[i]<=1$

从最小值跑到最大值

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int maxn=50009;
const int inf=1e9+7;
struct node{
    int v,w,nxt;
}e[maxn*3];
int head[maxn],d[maxn],vis[maxn],cnt,n,mn,mx;
void add(int u,int v,int w){
    e[++cnt].v=v;
    e[cnt].nxt=head[u];
    e[cnt].w=w;head[u]=cnt;
}
void spfa(){
    for(int i=mn;i<=mx;i++)d[i]=-inf;
    d[mn]=0;queue<int>q;
    q.push(mn);
    while(!q.empty()){
        int x=q.front();q.pop();vis[x]=0;
        for(int i=head[x];i;i=e[i].nxt){
            int y=e[i].v;
            if(d[y]<d[x]+e[i].w){
                d[y]=d[x]+e[i].w;
                if(!vis[y])q.push(y),vis[y]=1;
            }
        }
    }
}
int main(){
    while(~scanf("%d",&n)){
        cnt=0;
        memset(head,0,sizeof(head));
        memset(vis,0,sizeof(vis));
        memset(e,0,sizeof(e));
        for(int i=0,u,v,w;i<n;i++){
            scanf("%d%d%d",&u,&v,&w);
            add(u,v+1,w);
            mn=min(mn,u);
            mx=max(mx,v+1);
        }
        for(int i=mn;i<mx;i++){
            add(i,i+1,0);add(i+1,i,-1);
        }
        spfa();
        printf("%d",d[mx]);
    }
}