发布时间：2024-03-19

用法

求不等式组的可行解
求最大最小值

求不等式组的可行解

对于最短路的每次更新 $dis_v<=dis_u+c$ ,因此可以类比为形如 $x_i<=x_j+c$ 的不等式组，其中 $x_i,x_j$ 为自变量, $c$ 为常数

先将每个不等式组转化为边
找一个虚拟源点，可以遍历所有边
从源点求单源最短路
若有负环，则原不等式组无解；否则 $dis_i$ 为可行解

求最大最小值(每个变量的最大最小值)

求最大值，则求最短路
求最小值，则求最长路
对于一个确定的 $i$ $i$ 都可以放缩成若干个 $x_i<=x+c$ $x_{i} <= x + c$ 的形式，一定存在一个不等式 $x_i<=c即x=0(源点)$ $x_{i} <= c 即 x = 0 (源点)$ ,否则所有都是相对关系不可能有最值
- 求最大值为例
- $x_i<=x_j+c_1<=x_k+c_1+c_2<=...$
- 最大值即为每个上界的最小值
- 建立一个虚拟源点0,有0->i权值为c的边
- 所有点的最大上界都等于它到源点的边长，因此使用最短路求解， $dis_i$ 即为每个点的最大值总结：

建立关系
找出虚拟源点
求最长路最短路,判环是否有解

例题

[SCOI2011] 糖果

题目描述

幼儿园里有 $N$ 个小朋友， $\text{lxhgww}$ 老师现在想要给这些小朋友们分配糖果，要求每个小朋友都要分到糖果。但是小朋友们也有嫉妒心，总是会提出一些要求，比如小明不希望小红分到的糖果比他的多，于是在分配糖果的时候， $\text{lxhgww}$ 需要满足小朋友们的 $K$ 个要求。幼儿园的糖果总是有限的， $\text{lxhgww}$ 想知道他至少需要准备多少个糖果，才能使得每个小朋友都能够分到糖果，并且满足小朋友们所有的要求。

输入格式

输入的第一行是两个整数 $N$ ， $K$ 。接下来 $K$ 行，表示这些点需要满足的关系，每行 $3$ 个数字， $X$ ， $A$ ， $B$ 。

如果 $X=1$ ，表示第 $A$ 个小朋友分到的糖果必须和第 $B$ 个小朋友分到的糖果一样多；
如果 $X=2$ ，表示第 $A$ 个小朋友分到的糖果必须少于第 $B$ 个小朋友分到的糖果；
如果 $X=3$ ，表示第 $A$ 个小朋友分到的糖果必须不少于第 $B$ 个小朋友分到的糖果；
如果 $X=4$ ，表示第 $A$ 个小朋友分到的糖果必须多于第 $B$ 个小朋友分到的糖果；
如果 $X=5$ ，表示第 $A$ 个小朋友分到的糖果必须不多于第 $B$ 个小朋友分到的糖果；

输出格式

输出一行，表示 $\text{lxhgww}$ 老师至少需要准备的糖果数，如果不能满足小朋友们的所有要求，就输出 $-1$ 。

样例 #1

样例输入 #1

样例输出 #1

提示

对于 $30\%$ 的数据，保证 $N\leq100$

对于 $100\%$ 的数据，保证 $N\leq100000$

对于所有的数据，保证 $K\leq100000, 1\leq X\leq5, 1\leq A, B\leq N$

思路

最小值，即求最长路
$x=1:A>=B,B>=A$
$x=2:B>=A+1$
$x=3:A>=B$
$x=4:A>=B+1$
$x=5:B>=A$
虚拟源点： $所有人糖果大于等于1:x>=0+1$

cpp

vector<vector<array<int,2>>> adj;
int n,k;
vector<int> dis,cnt;
vector<bool> st;
bool spfa(){
    for(int i=1;i<=n;i++)dis[i]=-1e13;
    dis[0]=0;
    int tt=-1,hh=0;
    queue<int> q;
    q.push(0);
    st[0]=1;
    int count=0;
    while(q.size()){
        int u=q.front();
        q.pop();
        st[u]=0;
        for(auto [v,c]:adj[u]){
            if(dis[v]<dis[u]+c){
                dis[v]=dis[u]+c;
                cnt[v]=cnt[u]+1;
                if(++count>=1e6)return false;
                if(cnt[v]>=n+1)return false;
                if(!st[v]){
                    q.push(v);
                    st[v]=1;
                }
            }
        }
    }
    return true;
}
void solve(){
    cin>>n>>k;
    adj=vector<vector<array<int,2>>> (n+1);
    dis=vector<int>(n+1);
    cnt=vector<int>(n+1);
    st=vector<bool>(n+1);
    while(k--){
        int x,u,v;
        cin>>x>>u>>v;
        if(x==1){
            adj[u].push_back({v,0});
            adj[v].push_back({u,0});
        }
        else if(x==2){
            adj[u].push_back({v,1});
        }
        else if(x==3){
            adj[v].push_back({u,0});
        }
        else if(x==4){
            adj[v].push_back({u,1});
        }
        else{
            adj[u].push_back({v,0});
        }
    }
    for(int i=1;i<=n;i++)adj[0].push_back({i,1});
    if(!spfa())puts("-1");
    else{
        int ans=0;
        for(int i=1;i<=n;i++)ans+=dis[i];
        cout<<ans<<"\n";
    }
}

UVA1723 Intervals

题意：给定n个区间，每个区间至少选c个数，求满足所有条件至少需要多少个数思路：考虑前缀和建立关系

$s_r-s_{l-1}>=c$
$s_i>=s_{i-1}$
$s_{i-1}>=s_i-1$ 注意区间左值可以是0，不利于前缀和计算，所以对所有长度加1

cpp

vector<vector<array<int,2>>> adj;
int n,k;
vector<int> dis,cnt;
vector<bool> st;
bool spfa(){
    for(int i=1;i<=50001;i++)dis[i]=-1e15;
    dis[0]=0;
    queue<int> q;
    q.push(0);
    st[0]=1;
    while(q.size()){
        int u=q.front();
        q.pop();
        st[u]=0;
        for(auto [v,c]:adj[u]){
            if(dis[v]<dis[u]+c){
                dis[v]=dis[u]+c;
                if(!st[v]){
                    q.push(v);
                    st[v]=1;
                }
            }
        }
    }
    return true;
}
void solve(){
    cin>>n;
    adj=vector<vector<array<int,2>>> (N);
    dis=vector<int>(N);
    cnt=vector<int>(N);
    st=vector<bool>(N);
    for(int i=1;i<=50001;i++){
        adj[i-1].push_back({i,0});
        adj[i].push_back({i-1,-1});
    }
    for(int i=1;i<=n;i++){
        int a,b,c;
        cin>>a>>b>>c;
        a++,b++;
        adj[a-1].push_back({b,c});
    }
    spfa();
    cout<<dis[50001]<<"\n";
}

用法 ​

求不等式组的可行解 ​

求最大最小值(每个变量的最大最小值) ​

例题 ​

[SCOI2011] 糖果 ​

题目描述 ​

输入格式 ​

输出格式 ​

样例 #1 ​

样例输入 #1 ​

样例输出 #1 ​

提示 ​

思路 ​

UVA1723 Intervals ​

​

用法