题解：AT_abc277_h [ABC277Ex] Constrained Sums

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

定义

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 0]$ 一定成立。因此连边 $[x_i <0] \rightarrow [x_i \ge 0]$ 。
$[x_i < m+1]$ 一定成立。因此连边 $[x_i \ge m+1] \rightarrow [x < m+1]$ 。
如果 $[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]

成立即可。

CPP

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

题解：AT_abc277_h [ABC277Ex] Constrained Sums

文章操作

相关推荐

评论

题解：AT_abc277_h [ABC277Ex] Constrained Sums