Skip to content

Problem C: 伊菲的复习

📝 题目描述

🔑 算法模块

💡 思路分析

题意概括： \(n\) 个点，每个点有权值 \(a_i\) ，选择一个点有 \(v\) 的贡献，最后减去选择点乘积质因子和的代价，使贡献最大。

最大权闭合子图板子，桶排去重，源点往每个点建容量为 该点数量 \(\times\) \(v\) 的正权边，然后，对于每个点，往它们的每个质因子建容量无限的边，最后，每个质因子往汇点建容量为质因子大小的负权边（图意义上值还是正的）。用 \(nv\) 减去最大流即是答案。

把一个选点方案与它们影响到的质因子还有源点记为一个闭合子图 \(A\) ，那么 \(A\) 的权值 \(a\) 就是 \(A\) 的正权减去负权。

\(A\) 到除 \(A\) 以外的所有点构成的子图 \(B\) 的割 \(c\) 就是 \(A\) 的负权加上 \(B\) 的正权（具体为 \(A\) 里面的负权点与汇点，源点与 \(B\) 的正权点）。

\(a+c=\) \(A\) 的正权加上 \(B\) 的正权，也就是说 \(a=\) 正权和减去 \(c\) 。要使 \(a\) 最大，因为正权和不变，所以让 \(c\) 最小，也就是最小割。

根据最大流最小割原理，最大流等于最小割，也就是上面那玩意。

题外话

这道题本来 \(n\) 是 \(2\times 10^5\) 的，不知道是因为每个左部点连右部点的边很少还是什么 在自己出的任何样例下跑的飞快，但证明不了正确性改成了 \(2\times 10^2\)

有没有佬会证QAQ

🖥️ 代码实现

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int M = 1e6 + 10;
template<class T>
struct MaxFlow {
    struct Edge {
        int nxt, to, cap, ycap, sta, cost;
    };
    int n, cnt, s, t;
    vector<Edge>e;
    vector<int>h, head;
    MaxFlow();
    MaxFlow(int n) {
        init(n);
    }
    MaxFlow(int n, int m) {
        init(n, m);
    }
    void init(int n) {
        this->n = n;
        e = vector<Edge>((this->n + 1) << 1);
        head = vector<int>((this->n + 1) << 1, -1);
        cnt = -1;
    }
    void init(int n, int m) {
        this->n = n;
        e = vector<Edge>((m + 1) << 1);
        head = vector<int>((m + 1) << 1, -1);
        cnt = -1;
    }
    void add(int u, int v, int w) {
        e[++cnt] = {head[u], v, w, w, u, 0};
        head[u] = cnt;
        e[++cnt] = {head[v], u, 0, 0, v, 0};
        head[v] = cnt;
    }
    bool bfs() {
        h = vector<int>(n + 2, -1);
        h[s] = 0;
        queue<int>qu;
        qu.push(s);
        while (!qu.empty()) {
            int u = qu.front();
            qu.pop();
            for (int i = head[u]; i != -1; i = e[i].nxt) {
                int v = e[i].to;
                if (h[v] == -1 && e[i].cap) {
                    h[v] = h[u] + 1;
                    qu.push(v);
                }
            }
        }
        return h[t] != -1;
    }
    int dfs(int u, int f) {
        if (u == t)return f;
        int w, used = 0;
        for (int i = head[u]; i != -1; i = e[i].nxt) {
            int v = e[i].to;
            if (h[v] == h[u] + 1 && e[i].cap) {
                w = dfs(v, min(f - used, e[i].cap));
                e[i].cap -= w;
                e[i ^ 1].cap += w;
                if ((used += w) == f)return f;
            }
        }
        if (!used)h[u] = -1;
        return used;
    }
    int max_flow(int s, int t) {
        for (int i = 0; i <= cnt; i++)e[i].cap = e[i].ycap;
        int ans = 0;
        this->s = s;
        this->t = t;
        while (bfs())ans += dfs(s, 0x3f3f3f3f3f3f);
        return ans;
    }
};
int n, d = 0, js = 0, p[M], cnt = 0, kc = 0, a[M], sl[M], v, dd[M];
bool e[M];
MaxFlow<int>mf(1);
void pr(int n) {
    cnt = 0;
    for (int i = 1; i <= n; i++)e[i] = 0;
    for (int i = 2; i <= n; i++)if (!e[i]) {
            p[++cnt] = i;
            bool fl = 0;
            for (int j = 1; j * i <= n; j++) {
                e[i * j] = 1;
                if (a[i * j]) {
                    fl = 1;
                    mf.add(kc + a[i * j], dd[cnt], 1e12);
                }
            }
            if (fl)mf.add(dd[cnt], kc + d + 1, i);
        }
}
void pr1(int n) {
    cnt = 0;
    for (int i = 1; i <= n; i++)e[i] = 0;
    for (int i = 2; i <= n; i++)if (!e[i]) {
            cnt++;
            bool fl = 0;
            for (int j = 1; j * i <= n; j++) {
                e[i * j] = 1;
                if (a[i * j]) {
                    fl = 1;
                    js++;
                }
            }
            if (fl)dd[cnt] = ++kc;
        }
}
void solve() {
    cin >> n >> v;
    int si0 = 0;
    for (int i = 1; i <= n; i++) {
        int k;
        cin >> k;
        if (a[k] == 0 && k > 1)a[k] = ++d;
        if (k > 1)sl[k]++;
        if (k == 0)si0 = 1;
    }
    if (si0) {
        cout << n*v << "\n";
        return;
    }
    pr1(1e6);
    mf.init(kc + d + 2, js + kc + d + 10);
    for (int i = 2; i <= 1e6; i++)if (a[i])mf.add(0, kc + a[i], sl[i]*v);
    pr(1e6);
    cout << v*n - mf.max_flow(0, kc + d + 1) << "\n";
}
signed main() {
    ios::sync_with_stdio(0);
    cout.tie(0);
    cin.tie(0);
    solve();
}

⏱️ 复杂度分析

📚 拓展