题解 UVA1723 【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;
}

题解 UVA1723 【Intervals】

原文：https://www.cnblogs.com/juruoyqr/p/11518063.html