Intervals 题解

题目链接

本蒟蒻最近在复习图论，听机房里的大佬说这道题是一道差分约束裸题，就跑过来做了这道题。

简单介绍一下差分约束系统：差分约束系统就是给出n个变量 $x_{i}$，在m个形如 $x_{i}-x_{j}\le c_{k}$ 的不等式的约束下，求解所有满足这些不等式的解。

而查分约束系统可以通过图论解决。我们可以把每一个变量看做一个节点，而每个约束条件 $x_{i}-x_{j}\le c_{k}$ 可以视为 $j$ 节点到 $i$ 节点连了一条权值为$c_{k}$的有向边。

在这个图中，节点$i$到节点 $j$ 的最短路为 $x_{i}-x_{j}$ 的最大值，因为对于单源最短路径满足的三角不等式 $dis_{u}\le w(u,v)+dis_{v}$，在本图中为 $dis_{i}\le c_{k}+dis_{j}$，变形可得 $dis_{i}-dis_{j}\le c_{k}$，即节点 $i$ 到节点 $j$ 的最短路为 $x_{i}-x_{j}$ 的最大值。

再看这道题，要在区间 [$a_{i}$，$b_{i}$] 中至少取任意互不相同的 $c_{i}$ 个整数。我们不妨设p[k]为0到k之间选几个整数。由题意易得，$p[b_{i}]-p[a_{i}]\ge c_{i}$，而题意中又有一些隐藏条件：

1. $p[i]-p[i-1]\ge0$，即 $0$ 到 $k$ 中选出的数肯定大于等于 $0$到$k-1$中选出的数
2. $p[k-1]-p[k]\ge-1$，即每个数至多选一次。

我们还需要建立一个根节点，与所有节点相连且边权为0，这样就可以以根节点为出发点跑一个最短/长路了。

得到这些条件后，就可以建一个图，然后跑一遍从根节点出发的最长路（因为要求最小值），再输出$dis[max]$就可以了。

#include<bits/stdc++.h>
using namespace std;
int tot=0,dis[500003];
struct node{
    int v,k;
};
vector<node>head[500003];//邻接表

inline int read(){
    int s=0,g=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-')
            g=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        s=(s<<3)+(s<<1)+(ch^48);
        ch=getchar();
    }
    return s*g;
}
int max(int a,int b){
    if(a>b)
        return a;
    return b;
}

void spfa(int start){//spfa求最长路
    bool vis[500003];
    queue<int> que;
    que.push(start);
    for(int i=0;i<=tot;i++){
    	dis[i]=-0x7fffffff;
    	vis[i]=false;
    }
    vis[start]=true;
    dis[start]=0;

    while(!que.empty()){
        int num=que.front();
        que.pop();
        vis[num]=false;
        for(int i=0;i<head[num].size();i++){
            if(dis[head[num][i].v]<dis[num]+head[num][i].k){
                dis[head[num][i].v]=dis[num]+head[num][i].k;
                if(!vis[head[num][i].v]){
                	que.push(head[num][i].v);
                	vis[head[num][i].v]=true;
                }
            }
        }
    }
}

int main(){
    int n,a,b,c,t;
    node p;
    t=read();
    while(t){
        n=read();
    	for(int i=0;i<=50002;i++){
    		vector<node>().swap(head[i]);
        }//清空向量
        tot=0;

    	for(int i=0;i<n;i++){
            a=read(),b=read(),c=read();
            p.v=b;
            p.k=c;
            head[a-1].push_back(p);
            tot=max(b,tot);
        }//建图

        for(int i=1;i<=tot;i++){
            p.k=-1;
            p.v=i-1;
            head[i].push_back(p);//隐藏条件2

            p.k=0;
            p.v=i;
            head[i-1].push_back(p);//隐藏条件1

			head[50002].push_back(p);//我设50002号节点为根节点，连上所有节点
        }
        p.k=0;
        p.v=0;
        head[50002].push_back(p);
        spfa(50002);//spfa不是死了吗
        printf("%d\n",dis[tot]);
        if(--t)
        	cout<<endl;//注意这里的输出格式，特别坑，我wa了好多次才发现
    }
    return 0;
}