专栏文章

P12348 题解

LLittle_CartG2_leaf
P12348题解参与者 2已保存评论 2

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
2 条
当前快照
1 份
快照标识符
@miphf9g0
此快照首次捕获于
2025/12/03 12:03
3 个月前
此快照最后确认于
2025/12/03 12:03
3 个月前
查看原文

前言

无内鬼，来点差分约束。

思路

一眼差分约束（或者流），但是流好像不太行，那还是差分约束吧。
注意到 min⁡l≤x≤ra[x]−max⁡p≤y≤qa[y]≥ans\min\limits_{l \leq x \leq r} a[x] - \max\limits_{p \leq y \leq q} a[y] \geq ans 可以转换为 max⁡p≤y≤qa[y]≤min⁡l≤x≤ra[x]−ans\max \limits_{p\le y\le q} a[y] \le \min \limits_{l\le x\le r} a[x] - ans，这个形式简直就是差分约束板子。
直接暴力将 [l,r][l,r] 中的点向 [p,q][p,q] 连长度为 −ans-ans 的边的话，边数是 O(n×(r−l+1)×(q−p+1))O(n\times (r-l+1)\times(q-p+1)) 复杂度的，又因为 0≤r−l,q−p≤1000\le r-l,q-p\le 100，所以边数是 O(n×1002)O(n\times 100^2) 复杂度的，总复杂度达到 O(mn×1002)O(mn\times 100^2)，不太能过。
注意到我们可以在每次连边时建立一个中继点，先将 [l,r][l,r] 中的点向这个中继点连长度为 −ans-ans 的边，再将这个中继点向 [p,q][p,q] 连长度为 00 的边，边数会缩小至 O(n×(r−l+1+q−p+1))O(n\times (r-l+1+q-p+1)) 复杂度，即 O(n×200)O(n\times 200)，总复杂度为 O(mn×200)O(mn\times 200)，又因为不太能跑的很满，所以可以过。

代码

CPP
#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";
    }
}

评论

共 2 条评论，欢迎与作者交流。

正在加载评论...