题解：AT_abc277_h [ABC277Ex] Constrained Sums

reinforest · 2025-09-12 13:21:15 · 题解

对于这些赋值问题拆点似乎是一个常见套路。

定义 n \times (m+2) 个布尔变量，第 (i-1) \times (m+2) +j+1 个变量代表 [x_i \ge j]。

这相当于对于 x_i 拆成 m+2 个变量，对于每一个变量 x_{i,j} 有 2 个状态：要么 \ge j，要么 <j。此外，这些点是有基本限制的。

• 如果 [x_i \ge j] 成立，那么 [x_i \ge j-1] 一定成立。因此连边 [x_i \ge j] \rightarrow [x_i \ge j-1]。
• 如果 [x_i < j] 成立，那么 [x_i < j+1] 一定成立。因此连边 [x_i < j] \rightarrow [x_i < j+1]。

然后考虑题目限制。对于限制 L \le x_a+x_b \le R，先考虑枚举 x_a 的取值。

• 若 x_a \ge j，那么 x_b < R-j+1。因此连边 [x_a \ge j] \rightarrow [x_b < R-j+1]。
• 若 x_a < j，那么 x_b \ge L-j+1。因此连边 [x_a < j] \rightarrow [x_b \ge L-j+1]。

注意这些连边还有对应的对偶的情况。（因为 2-SAT 建图一个命题已经在连边中体现了，也需要保证其逆否命题在连边中体现。）

然后也需要考虑枚举 x_b 的取值，连边的情况也是一样的。

最后把边建出来跑 2-SAT 即可。跑出来后构造方案时，对于每一个 i，我们只需要找到最小的 j 使得 [x_i \ge j] 成立即可。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
constexpr ll maxn=4e6+5;
ll n,m,q,stk[maxn],dfn[maxn],bel[maxn],low[maxn],tot,tp,scnt;
vector<ll> G[maxn];
bool vis[maxn];
ll id(ll cur,ll num,ll opt){
    return (cur-1)*(m+2)+num+1+opt*n*(m+2);
}
void Tarjan(int x){
    dfn[x]=low[x]=++tot;
    stk[++tp]=x;
    vis[x]=true;
    for(auto v:G[x]){
        if(!dfn[v]){
            Tarjan(v);
            low[x]=min(low[x],low[v]);
        }else if(vis[v])low[x]=min(low[x],dfn[v]);
    }
    if(dfn[x]==low[x]){
        scnt++;
        while(vis[x]){
            bel[stk[tp]]=scnt;
            vis[stk[tp--]]=false;
        }
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m>>q;
    for(int i=1;i<=n;i++){
        G[id(i,0,1)].push_back(id(i,0,0));
        G[id(i,m+1,0)].push_back(id(i,m+1,1));
        for(int j=0;j<=m;j++){
            G[id(i,j+1,0)].push_back(id(i,j,0));
            G[id(i,j,1)].push_back(id(i,j+1,1));
        }
    }
    while(q--){
        ll a,b,l,r;
        cin>>a>>b>>l>>r;
        for(int j=1;j<=m;j++){
            ll resr=min(m+1,max(0ll,r-j+1)),resl=min(m+1,max(0ll,l-j+1));
            G[id(a,j,0)].push_back(id(b,resr,1));
            G[id(b,j,0)].push_back(id(a,resr,1));
            G[id(a,resr,0)].push_back(id(b,j,1));
            G[id(b,resr,0)].push_back(id(a,j,1));
            G[id(a,j,1)].push_back(id(b,resl,0));
            G[id(b,j,1)].push_back(id(a,resl,0));
            G[id(a,resl,1)].push_back(id(b,j,0));
            G[id(b,resl,1)].push_back(id(a,j,0));
        }
    }
    for(int i=1;i<=2*n*(m+2);i++)if(!dfn[i])Tarjan(i);
    for(int i=1;i<=n;i++){
        for(int j=0;j<=m+1;j++){
            if(bel[id(i,j,0)]==bel[id(i,j,1)]){
                cout<<-1<<"\n";
                return 0;
            }
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=0;j<=m;j++){
            if(bel[id(i,j,0)]<bel[id(i,j,1)] && bel[id(i,j+1,0)]>bel[id(i,j+1,1)]){
                cout<<j<<" ";
                break;
            }
        }
    }
    return 0;
}