题解：CF1630F Making It Bipartite

· · 题解

更好的阅读体验

题目的边用的是倍数关系（偏序）。
当 x \rarr y, y \rarr z，就必然有 x \rarr z。
为了避免这种情况，意味着每个点要么只有因数，要么只有倍数。

我们将每个点拆成两个点，x_0 表示图中 x 只能保留其的因数，x_1 表示其倍数。
再用一条边 (x, y) 表示 x 和 y 点最多保留 1 个。
所以肯定先连 (x_0, x_1)。

再想不同的两个点之间。
为方便这里假设 y \mid x。
除了 x_0 和 y_1 可以同时存在，其他都是错误的。
那么我们需要 3 条边，分别是 x_0 \rarr y_0, x_1 \rarr y_1, x_1 \rarr y_0。

所以答案就是这个图的最大独立集了。

不对！最大独立集目前可没有多项式求解的方法。
不可做，结束!
但这个是偏序集，我们如果将边定向，变成 DAG 那么答案就是最长反链了。
再根据 Dilworth 定理转化成最少链覆盖，就可解了。

可是怎么定向呢？有一个显然的做法，我们将大的数指向小的数，这样必然没有环。 

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define FL(a, b, c) for(int a = (b), a##end = (c); a <= a##end; a++)
#define FR(a, b, c) for(int a = (b), a##end = (c); a >= a##end; a--)
#define lowbit(x) ((x) & -(x))
#define eb emplace_back
constexpr int N = 5e5 + 10;
int tot = 1, head[N], dis[N], a[N], s, t, ans, now[N];
struct edge{
    int v, nxt, w;
}e[6000000];
int n;
#define id(x, i, j) (x + i * 2 * n + j * n)
void add(int u, int v){
    e[++tot] = {v, head[u], 1}, head[u] = tot;
    e[++tot] = {u, head[v], 0}, head[v] = tot;
}
void Add(int u, int v){
    add(id(u, 0, 0), id(v, 0, 1));
    add(id(u, 0, 0), id(v, 1, 1));
    add(id(u, 1, 0), id(v, 1, 1));
}
bool bfs(){
    queue<int>q;
    FL(i, s, t)dis[i] = 0;
    dis[s] = 1, q.emplace(s);
    while(!q.empty()){
        for(int x = q.front(), i = (now[x] = head[x]), v; i; i = e[i].nxt)
            if(e[i].w && !dis[v = e[i].v])dis[v] = dis[x] + 1, q.emplace(v);
        q.pop();
    }
    return dis[t];
}
int dfs(int x, int last){
    if(x == t)return last;
    int res = last, k;
    for(int i = now[x], v; i && res; i = e[i].nxt)
        if(e[now[x] = i].w && dis[v = e[i].v] == dis[x] + 1)
            if(k = dfs(v, min(res, e[i].w)))e[i].w -= k, res -= k, e[i ^ 1].w += k;
            else dis[v] = 0;
    return last - res;
}
void solve(){
    cin >> n;
    memset(dis, 0, (sizeof*dis) * 100000);
    tot = 1, ans = s = 0, t = n * 4 + 1;
    FL(i, s, t)head[i] = 0;
    FL(i, 1, n)cin >> a[i], dis[a[i]] = i;
    FL(i, 1, n){
        add(id(i, 0, 0), id(i, 1, 1));
        add(s, id(i, 0, 0)), add(s, id(i, 1, 0));
        add(id(i, 0, 1), t), add(id(i, 1, 1), t);
    }
    FL(i, 1, 5e4)if(dis[i])FL(j, 2, (int)(5e4) / i)if(dis[j * i])Add(dis[j * i], dis[i]);
    while(bfs())ans += dfs(s, 1e9);
    cout << ans - n << endl;
}
int32_t main(){
    cin.tie(0)->sync_with_stdio(0);
    int t;
    cin >> t;
    while(t--)solve();
    return 0;
}