题解：P11453 [USACO24DEC] Deforestation S

· · 题解

思路

将所有数进行离散化，很显然一道差分约束模板。s_i 表示有多少个 1-i 的数，题目给了 k 个约束，即：

s_{r_i}-s_{{l_i}-1} \ge t_i

将 l_i-1 与 r_i 连一条边权为 t_i 的边，跑个最长路。但是关于 SPFA，它四了。

没有关系，加一个优化即可卡过此题。

最后附上丑陋的代码。

代码

#include<algorithm>
#include<iostream>
#include<cstring>
#include<vector>
#include<deque>
#define int long long
using namespace std;
const int N=300005,INF=1145141919;
int T,n,k,u,v,w,st,en,d[N],x[N];
bool vis[N];
deque<int> q;
vector<pair<int,int> > t[N];
void SLF(){
    if(q.size()&&d[q.front()]<d[q.back()])swap(q.front(),q.back());
}
void SPFA(int st){
    memset(d,-0x3f,sizeof(d));
    memset(vis,false,sizeof(vis));
    d[st]=0;
    q.push_back(st);
    while(q.size()){
        int x=q.front();
        q.pop_front();
        vis[x]=false;SLF();
        for(int i=0;i<t[x].size();i++){
            int y=t[x][i].first,w=t[x][i].second;
            if(d[y]<d[x]+w){
                d[y]=d[x]+w;
                if(!vis[y]){
                    vis[y]=true;
                    q.push_back(y);
                    SLF();
                }
            }
        }
    }
}
signed main(){
    cin>>T;
    while(T--){
        cin>>n>>k;
        st=INF;en=-INF;
        for(int i=1;i<=n;i++)cin>>x[i];
        for(int i=0;i<=n+1;i++)t[i].clear();
        sort(x+1,x+n+1);
        while(k--){
            cin>>u>>v>>w;
            u=lower_bound(x+1,x+n+1,u)-x;
            v=upper_bound(x+1,x+n+1,v)-x-1;
            st=min(st,u-1);en=max(en,v);
            t[u-1].push_back(make_pair(v,w));
        }
        for(int i=st+1;i<=en;i++){
            t[i].push_back(make_pair(i-1,-1));
            t[i-1].push_back(make_pair(i,0));
        }
        SPFA(st);
        cout<<n-d[en]<<"\n";
    }
    return 0;
}