题解 UVA1723 【Intervals】
逃离地球
2019-07-22 00:37:14
本蒟蒻最近在复习图论，听机房里的大佬说这道题是一道差分约束裸题，就跑过来做了这道题。
简单介绍一下差分约束系统：**差分约束系统**就是给出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]$就可以了。
```cpp
#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;
}
```