P12348 题解

Little_Cart · 2025-04-27 13:37:49 · 题解

前言

无内鬼，来点差分约束。

思路

一眼差分约束（或者流），但是流好像不太行，那还是差分约束吧。

注意到 \min\limits_{l \leq x \leq r} a[x] - \max\limits_{p \leq y \leq q} a[y] \geq ans 可以转换为 \max \limits_{p\le y\le q} a[y] \le \min \limits_{l\le x\le r} a[x] - ans，这个形式简直就是差分约束板子。

直接暴力将 [l,r] 中的点向 [p,q] 连长度为 -ans 的边的话，边数是 O(n\times (r-l+1)\times(q-p+1)) 复杂度的，又因为 0\le r-l,q-p\le 100，所以边数是 O(n\times 100^2) 复杂度的，总复杂度达到 O(mn\times 100^2)，不太能过。

注意到我们可以在每次连边时建立一个中继点，先将 [l,r] 中的点向这个中继点连长度为 -ans 的边，再将这个中继点向 [p,q] 连长度为 0 的边，边数会缩小至 O(n\times (r-l+1+q-p+1)) 复杂度，即 O(n\times 200)，总复杂度为 O(mn\times 200)，又因为不太能跑的很满，所以可以过。

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define PII pair<int,int>
#define fi first
#define se second
#define mkp make_pair
const int N=300024;
int t,n,m,tot;
vector<PII> e[N];
int dis[N],cnt[N];
queue<int> q;
bool spfa(){
    while(!q.empty()){
        q.pop();
    }
    for(int i=1;i<=n+m;i++){
        q.push(i);
    }
    while(!q.empty()){
        tot++;
        int u=q.front();
        q.pop();
        if(cnt[u]>=m+n+2||tot>10000000){
            return 0;
        }
        cnt[u]++;
        for(PII tp:e[u]){
            int v=tp.fi,w=tp.se;
            if(dis[u]+w<dis[v]){
                dis[v]=dis[u]+w;
                q.push(v);
            }
        }
    }
    return 1;
}
signed main(){
    cin>>m>>n;
    for(int i=1;i<=m;i++){
        int l,r,x,y,w;
        cin>>l>>r>>x>>y>>w;
        for(int j=l;j<=r;j++){
            e[j].push_back(mkp(n+i,-w));
        }
        for(int j=x;j<=y;j++){
            e[n+i].push_back(mkp(j,0));
        }
    }
    if(spfa()){
        int mx=dis[1],mn=dis[1];
        for(int i=2;i<=n+m;i++){
            mx=max(mx,dis[i]);
            mn=min(mn,dis[i]);
        }
        cout<<mx-mn;
    }
    else{
        cout<<"No Solution";
    }
}