差分约束

敦爷讲图论的时候讲到了，所以来补一补

POJ-1201

条件不难找：

0<=dis[i]-dis[i-1]<=1

dis[b[i]]-dis[a[i]-1]>=c[i]

但是直接最短路跑出的是最大解，然而题目需要的是最小解，所以要取负跑最短路，或者跑最长路，不过在两种情况下要注意优先队列的排列顺序是正好相反的，不然有可能被t掉

最短路取负

此时要将队列从大到小排

#include<iostream>
#include<sstream>
#include<iomanip>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<stack>
#include<vector>
#include<string>
#include<map>
#include<set>
#include<ctime>
#include<bitset>
#include<iterator>
#define bug cout<<"-----------"<<endl;
#define ll  long long
#define ull unsigned long long
using namespace std;
const int N=1e5+5,M=1e9+7;
const ull base=13331;
const double Pi=acos(-1.0);
const ll C=299792458;
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int a[N],b[N],c[N];
int head[N],ver[N*2],edge[N*2],Next[N*2],tot=0;
void add(int x,int y,int w){
    ver[++tot]=y,edge[tot]=w;
    Next[tot]=head[x],head[x]=tot;
}
struct node{
    int x,d;
    friend bool operator<(node m,node n){
        return m.d<n.d;
    }
};
int v[N],dis[N];
void spfa(int p){
    memset(dis,0x3f,sizeof(dis));
    priority_queue<node> Q;
    Q.push({p,0});
    dis[p]=0;
    v[p]=1;
    while(!Q.empty()){
        int x=Q.top().x;
        Q.pop();
        v[x]=0;
        for(int i=head[x];i;i=Next[i]){
            int y=ver[i],w=edge[i];
            if(dis[y]>dis[x]+w){
                dis[y]=dis[x]+w;
                if(v[y]==0){
                    Q.push({y,dis[y]});
                    v[y]=1;
                }
            }
        }
    }
}
int main(){
    ios::sync_with_stdio(false);
    int n;
    cin>>n;
    int maxx=0;
    for(int i=1;i<=n;i++){
        cin>>a[i]>>b[i]>>c[i];
        a[i]++,b[i]++;
        maxx=max(maxx,a[i]-1);
        maxx=max(maxx,b[i]);
    }
    for(int i=1;i<=n;i++){
        add(a[i]-1,b[i],-c[i]);
    }
    for(int i=1;i<=maxx;i++){
        add(i,i-1,1);
        add(i-1,i,0);
    }
    spfa(0);
    cout<<-dis[maxx]<<endl;
}
//最短路直接跑只能算出最大解
//本题算最小解需要对差分值取负

//0<=-(dis[i]-dis[i-1])<=1
//-1<=dis[i]-dis[i-1]<=0
//dis[i]<=dis[i-1]
//dis[i-1]<=dis[i]+1

//-(dis[b[i]]-dis[a[i]-1])>=c[i]
//dis[b[i]]-dis[a[i]-1]<=-c[i]
//dis[a[i]-1]-c[i]>=dis[b[i]]

最长路

此时要将队列从小到大排

#include<iostream>
#include<sstream>
#include<iomanip>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<stack>
#include<vector>
#include<string>
#include<map>
#include<set>
#include<ctime>
#include<bitset>
#include<iterator>
#define bug cout<<"-----------"<<endl;
#define ll  long long
#define ull unsigned long long
using namespace std;
const int N=1e5+5,M=1e9+7;
const ull base=13331;
const double Pi=acos(-1.0);
const ll C=299792458;
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int a[N],b[N],c[N];
int head[N],ver[N*2],edge[N*2],Next[N*2],tot=0;
void add(int x,int y,int w){
    ver[++tot]=y,edge[tot]=w;
    Next[tot]=head[x],head[x]=tot;
}
struct node{
    int x,d;
    friend bool operator<(node m,node n){
        return m.d>n.d;
    }
};
int v[N],dis[N];
void spfa(int p){
    memset(dis,-0x3f,sizeof(dis));
    priority_queue<node> Q;
    Q.push({p,0});
    dis[p]=0;
    v[p]=1;
    while(!Q.empty()){
        int x=Q.top().x;
        Q.pop();
        v[x]=0;
        for(int i=head[x];i;i=Next[i]){
            int y=ver[i],w=edge[i];
            if(dis[y]<dis[x]+w){
                dis[y]=dis[x]+w;
                if(v[y]==0){
                    Q.push({y,dis[y]});
                    v[y]=1;
                }
            }
        }
    }
}
int main(){
    ios::sync_with_stdio(false);
    int n;
    cin>>n;
    int maxx=0;
    for(int i=1;i<=n;i++){
        cin>>a[i]>>b[i]>>c[i];
        a[i]++,b[i]++;
        maxx=max(maxx,a[i]-1);
        maxx=max(maxx,b[i]);
    }
    for(int i=1;i<=n;i++){
        add(a[i]-1,b[i],c[i]);
    }
    for(int i=1;i<=maxx;i++){
        add(i,i-1,-1);
        add(i-1,i,0);
    }
    spfa(0);
    cout<<dis[maxx]<<endl;
}