ARC146D

云浅知处 · 2024-01-11 11:10:03 · 题解

先考虑怎么判合法，将限制改写为：

• A_{P_i}\le X_i\iff A_{Q_i}\le Y_i
• A_{P_i}\ge X_i\iff A_{Q_i}\ge Y_i

不难发现和原来是等价的。那么写出变量 x_{i,j}=[A_i\le j],y_{i,j}=[A_i\ge j]，建图：

• x_{i,j}\to x_{i,j+1},y_{i,j}\to y_{i,j-1}
• x_{i,j}\to \lnot\ y_{i,j+1},y_{i,j}\to \lnot\ x_{i,j-1}
• x_{P_i,X_i}\iff x_{Q_i,Y_i},y_{P_i,X_i}\iff y_{Q_i,Y_i}

可以发现有用的点数只有 O(N+M) 个，对这些点连边建图跑 2sat 即可。

现在考虑怎么求出和最小的一组，可以发现这一堆下界之类的应该同时取到，那直接尽量给 x 赋值为 1，给 y 赋值成 0 就好了。怎么判定能不能给 x 赋值成 1 呢，这个就类似求 2sat 字典序最小解，从前往后依次 dfs 就行。

实现的时候其实可以注意到 x_{i,j}=\lnot\ y_{i,j+1}，于是只对 x 连边就行。

#include<bits/stdc++.h>

#define ll long long
#define mk make_pair
#define fi first
#define se second

using namespace std;

inline int read(){
    int x=0,f=1;char c=getchar();
    for(;(c<'0'||c>'9');c=getchar()){if(c=='-')f=-1;}
    for(;(c>='0'&&c<='9');c=getchar())x=x*10+(c&15);
    return x*f;
}

const int N=5e6+5;
int n,m,k;
vector<int>vals[N],id[N];
vector<int>G[N];
struct E{int u,v,x,y;};
vector<E>edges;

#define tr(x) (2*x)
#define fs(x) (2*x+1)
void adde(int x,int y){// x => y
    G[x].emplace_back(y);
    G[y^1].emplace_back(x^1);
}
bool mark[N];
vector<int>S;
bool dfs(int u){
    if(mark[u])return true;
    if(mark[u^1])return false;
    mark[u]=1;S.emplace_back(u);
    for(int v:G[u])if(!dfs(v))return false;
    return true;
}

signed main(void){

#ifndef ONLINE_JUDGE
    freopen("in.in","r",stdin);
#endif

    n=read(),m=read(),k=read();
    for(int i=1;i<=k;i++){
        int u=read(),x=read(),v=read(),y=read();
        edges.emplace_back((E){u,v,x,y}),edges.emplace_back((E){u,v,x-1,y-1});
        vals[u].emplace_back(x),vals[v].emplace_back(y);
        vals[u].emplace_back(x-1),vals[v].emplace_back(y-1);
    }
    for(int i=1;i<=n;i++)vals[i].emplace_back(0),vals[i].emplace_back(m);
    int ncnt=0;
    for(int i=1;i<=n;i++){
        sort(vals[i].begin(),vals[i].end());
        vals[i].resize(unique(vals[i].begin(),vals[i].end())-vals[i].begin());
        id[i].resize(vals[i].size());
        for(int j=0;j<vals[i].size();j++)id[i][j]=ncnt++;
        for(int j=0;j+1<vals[i].size();j++)adde(tr(id[i][j]),tr(id[i][j+1]));
        adde(tr(id[i][0]),fs(id[i][0])),adde(fs(id[i].back()),tr(id[i].back()));
    }
    for(auto [u,v,x,y]:edges){
        int px=lower_bound(vals[u].begin(),vals[u].end(),x)-vals[u].begin();
        int py=lower_bound(vals[v].begin(),vals[v].end(),y)-vals[v].begin();
        x=id[u][px],y=id[v][py],adde(tr(x),tr(y)),adde(tr(y),tr(x));
    }

    for(int i=0;i<2*ncnt;i+=2){
        if(mark[i]||mark[i^1])continue;
        S.clear();
        if(!dfs(i)){
            for(int y:S)mark[y]=0;S.clear();
            if(!dfs(i+1))return puts("-1"),0;
        }
    }

    ll ans=0;
    for(int i=1;i<=n;i++){
        for(int j=0;j<id[i].size();j++){
            if(mark[tr(id[i][j])]){ans+=vals[i][j-1]+1;break;}
        }
    }
    cout<<ans<<endl;

    return 0;
}