题解：AT_abc404_g [ABC404G] Specified Range Sums

· · 题解

终于，我打开了那场比赛，发现，我卡在了 EF，却没做 G，悲。

看到 \sum，显然是要进行前缀和，设 b_i = \sum_{j = 1}^i A_i，那么：

\sum_{j = L_i}^{R_i} A_i = b_{R_i}-b_{L_i-1}

此时转化：

\sum_{j = L_i}^{R_i} A_i = S_i \Downarrow b_{R_i}-b_{L_i-1} = s \Downarrow b_{R_i}-b_{L_i-1} \le s,b_{R_i}-b_{L_i-1} \ge s \Downarrow b_{R_i}-b_{L_i-1} \le s,b_{L_i-1}-b_{R_i} \le -s

很容易发现这是一个非常经典的差分约束，于是直接建图，跑一遍 SPFA 即可。 ::::warning[注意] 考虑到 A_i>0，所以 A_i \ge 1，于是 b_i-b_{i-1} \ge 1，等价于 b_{i-1}-b_i \le -1，所以这种边也需要建。这题超级源点可以建也可以不建，如果建的话注意是 n+1，因为 0 已经被占用了。 :::: ::::error[重点注意] 十年 OI 一场空，不开 long long 见祖宗！！

注意判断负环（即无解）情况！！

重中之重，这道题可以使用最长路，就不需要那么麻烦，不过如果使用的是最短路的话，答案也需要乘上 -1，因为图中有负边权，答案一定是负数，考虑 b_i 的走向其实是越来越大，也就是说其实最终的 b_n 其实是负数中的最大值，那么 -b_n 其实就是正数中的最小值，也就是答案。 :::: ::::success[Code] 这是超级源点加上最短路的做法。

#include<bits/stdc++.h>
using namespace std;
const int N = 4e3+5;
struct node
{
    int x;
    int w;
};
vector<node>a[N];
long long d[N];
int vis[N];
int num[N];
signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n,m;
    cin >> n >> m;
    for(int i = 1;i<=n;++i)
    {
        a[i-1].push_back({i,-1});
    }
    for(int i = 1;i<=m;++i)
    {
        int x,y,z;
        cin >> x >> y >> z;
        a[y].push_back({x-1,z});
        a[x-1].push_back({y,-z});
    }
    for(int i = 0;i<=n;++i)
    {
        a[n+1].push_back({i,0});
    }
    memset(d,0x7f,sizeof(d));
    queue<int>q;
    vis[n+1] = 1;
    q.push(n+1);
    d[n+1] = 0;
    while(q.size())
    {
        int x = q.front();
        q.pop();
        vis[x] = 0;
        for(node v:a[x])
        {
            if(d[x]+v.w<d[v.x])
            {
                d[v.x] = d[x]+v.w;
                if(!vis[v.x])
                {
                    vis[v.x] = 1;
                    q.push(v.x);
                    ++num[v.x];
                    if(num[v.x] == n+1)
                    {
                        cout << -1;
                        return 0;
                    }
                }
            }
        }
    }
    cout << -d[n];
    return 0;
}

::::