题解：P10934 西瓜种植

ivyjiao · 2024-09-23 20:56:13 · 题解

一本通提高篇的题居然还能写题解。

六倍经验：P1250，P1645，P1986，P10934，SP116，UVA1723。

一觉醒来，差分约束都成黄题了？

差分约束是一种特殊的 n 元一次不等式，包含 n 个变量及 m 个约束式子，每个约束式子由两个变量作差构成，每个式子形如 a_i-a_j\geq k，k 是常数，1\leq i,j\leq n。

而我们看本题，我们先对我们选完的数列进行一个前缀和 s_i=\sum_{j=1}^{j\leq i} d_j，d 中 1 表示选了，0 表示没选，那么本题对于每个限制，很明显有个式子 s_{b_i}-s_{a_i-1}\geq c_i，我们把每个 i 抽象成一个节点，那么这就是一个差分约束了，跑一遍 SPFA 求最长路来求解。

然而这样是错的，由于前缀和的性质，s_i \geq s_{i-1}，因为每个数只能选一次，所以 s_i-s_{i-1} 要么为 0，要么为 1，由此我们得到：s_i-s_{i-1}\geq 0,s_{i-1}-s_i\geq -1。

为了防止下标出现负数，我们把下标统一 +1。

在一次 SPFA 的松弛操作后，dis_v-dis_u\geq w，与不等式 s_{b_i}-s_{a_i-1}\geq c_i 性质一样，所以 SPFA 可以求出最小值，又因为解不等式同大取大原则，所以要求出最长路。

代码，半年前的牢代码了，码风有点差，还请见谅：

#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
int n,m,u,v,w,dis[50001],maxn;
vector<pair<int,int> >G[50001];
queue<int>q;
int main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        cin>>u>>v>>w;
        G[u].push_back({w,v+1});
    }
    for(int i=0;i<=n;i++){
        G[i+1].push_back({-1,i});
        G[i].push_back({0,i+1});
    }
    memset(dis,-1,sizeof dis);
    dis[0]=0;
    q.push(0);
    while(q.size()){
        int u=q.front();
        q.pop();
        for(int i=0;i<G[u].size();i++){
            if(dis[G[u][i].se]<dis[u]+G[u][i].fi){
                dis[G[u][i].se]=dis[u]+G[u][i].fi;
                q.push(G[u][i].se);
            }
        }
    }
    cout<<dis[n+1];
}