[Medium-Hard] CF1630F Making It Bipartite

xiezheyuan2025/2/25约 1169 字大约 6 分钟

咋就 *3400 了；讲个笑话：调了一个小时，结果是忘记链式前项星初值赋为 $1$ 了。

简要题意

给定一个长度为 $n$ 的序列 $a$ ，构造一个图，若 $a_i\mid a_j$ ，连边 $(i,j)$ 。你需要删去最少的点，使得原图变为一个二分图，输出删除的点数。

多组数据。 $1\leq \sum n,a_i\leq 5\times 10^7$ 。

思路

首先将“删除最少的点”改为“保留最多的点”。那么我们相当于要选择一个点集，使得这个点集的导出子图不存在长度大于 $1$ 的链。

不存在长度大于 $1$ 的链难以处理，不过不存在熟悉的（独立集）。考虑给图任意定向，则点集中的每个点，要么在导出子图中只有入度，要么只有出度。也就是说每个点有两种属性，所以考虑拆点。

将点 $u$ 拆成做出点的点 $\mathrm{Out}(u)$ 和做入点的点 $\mathrm{In}(u)$ 。然后尝试将其转为独立集问题。

对于在原图定向后的边 $(u,v)$ ：

连边 $(\mathrm{Out}(u),\mathrm{In(u)}),(\mathrm{Out}(v),\mathrm{In(v)})$ 表示一个点只能有一个属性。
连边 $(\mathrm{Out}(u),\mathrm{Out}(v)),(\mathrm{In}(u),\mathrm{In}(u))$ 表示相邻两点不能拥有同样的属性。
连边 $(\mathrm{In}(u),\mathrm{Out}(v))$ 表示限制边的方向。

那么我们需要找到建出的新图的最大独立集。一般图最大独立集问题是 NP-Hard 的，并且这个图显然不是二分图，目前我们似乎没有什么好的性质。

不过别忘了我们给图定了向，如果定向成的图构成了一个偏序集，那么我们有一个和独立集非常像的东西——反链。而根据 Dilworth 定理，最长反链等于最小链覆盖，而 DAG 的最小链覆盖问题是经典二分图匹配建模。所以现在只需要将图定向为一个偏序集形 DAG 即可。

考虑钦定大小关系，从较小的 $a_u$ 拆出的点，连向较大的 $a_v$ ，然后对于 $u$ 相同的边，钦定方向 $\mathrm{In}(u)\to \mathrm{Out}(u)$ 。我们需要证明，这样建出的图满足偏序集关系：

反对称性：由于这样定向出的图显然是 DAG，所以反对称性满足。
传递性：首先倍数关系满足传递性，现在只需要让 $\mathrm{In},\mathrm{Out}$ 关系也满足传递性。如果 $a\preceq b,b\preceq c$ ，且 $a$ 是一个 $\mathrm{In}$ ，则无论 $c$ 是什么， $a,c$ 都存在边。否则， $b,c$ 一定是 $\mathrm{Out}$ 。 $a,c$ 也存在边。

证毕。于是只需要建出定向后的 DAG，跑一遍最小链覆盖，就是保留点的最大值了。时间复杂度 $O(\mathrm{maxflow}(n,V\log V))$ 。

代码

#include <bits/stdc++.h>
using namespace std;

struct MaxFlow {
    struct node{
        int nxt, to, cap;
    };

    vector<node> g;
    vector<int> head, dep, cur;
    int S, T;

    void init(int n){
        head.clear(), head.resize(n + 1);
        dep.clear(), dep.resize(n + 1);
        cur.clear(), cur.resize(n + 1);
        g.clear(), g.push_back({0, 0, 0}), g.push_back({0, 0, 0});
    }

    void add(int u, int v, int c){
        g.push_back({head[u], v, c}), head[u] = g.size() - 1;
        g.push_back({head[v], u, 0}), head[v] = g.size() - 1;
    }

    bool bfs(){
        for(int& v : dep) v = 0;
        queue<int> q;
        q.push(S), dep[S] = 1;
        while(!q.empty()){
            int u = q.front();
            q.pop();
            for(int i=head[u];i;i=g[i].nxt){
                int v = g[i].to;
                if(!dep[v] && g[i].cap) q.push(v), dep[v] = dep[u] + 1;
            }
        }
        return dep[T];
    }

    int dfs(int u, int flow){
        if(u == T) return flow;
        for(int &i=cur[u];i;i=g[i].nxt){
            int v = g[i].to;
            if(dep[v] == dep[u] + 1 && g[i].cap){
                int t = dfs(v, min(flow, g[i].cap));
                if(t) return g[i].cap -= t, g[i ^ 1].cap += t, t;
            }
        }
        return 0;
    }

    int operator()(int s, int t){
        S = s, T = t;
        int mxflow = 0;
        while(bfs()){
            copy(head.begin(), head.end(), cur.begin());
            int x = 0;
            while((x = dfs(S, numeric_limits<int>::max()))) mxflow += x;
        }
        return mxflow;
    }
};

const int N = 5e4 + 5;
int n, a[N], bkt[N];
MaxFlow mf;

void add(int u, int v){
    mf.add(u << 1, v << 1 | 1, 1);
}

void solve(){
    cin >> n;
    for(int i=1;i<=n;i++) cin >> a[i], bkt[a[i]] = i;
    int m = *max_element(a + 1, a + n + 1);
    mf.init(((n << 1 | 1) << 1 | 1) + 1);
    for(int i=1;i<=m;i++){
        if(!bkt[i]) continue;
        int x = bkt[i] << 1, y = (bkt[i] << 1) | 1;
        add(x, y);
        for(int j=i<<1;j<=m;j+=i){
            if(!bkt[j]) continue;
            int a = bkt[j] << 1, b = (bkt[j] << 1) | 1;
            add(x, a), add(x, b), add(y, b);
        }
    }
    int S = 1, T = 2;
    for(int i=1;i<=n;i++){
        mf.add(S, (i << 1) << 1, 1);
        mf.add(S, (i << 1 | 1) << 1, 1);
        mf.add((i << 1) << 1 | 1, T, 1);
        mf.add((i << 1 | 1) << 1 | 1, T, 1);
    }
    int ret = mf(S, T);
    cout << ret - n << '\n';
    for(int i=1;i<=n;i++) bkt[a[i]] = 0;
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int t; cin >> t;
    while(t--) solve();
    return 0;
}

// Written by xiezheyuan

Submission。