「BZOJ 3275」Number - 最小割

有个正整数，需要从中选出一些数，使这些数的和最大。

若两个数同时满足以下条件，则不能同时被选。

存在正整数，使；
。

链接

BZOJ 3275
COGS 1389

题解

建图，把不能同时选择的数字连边，染色后发现是二分图，问题转化为二分图最大点权独立集。

从源点到所有点连边，容量为数字，从所有点向汇点连边，容量为数字，不能成对选择数字，从点到点连边，容量为正无穷，求出最小割即为损失，总和减去损失即为答案。

代码

#include <cstdio>
#include <cassert>
#include <climits>
#include <cmath>
#include <algorithm>
#include <queue>

const int MAXN = 3000;

struct Node;
struct Edge;

struct Node {
    Edge *e, *c;
    int l;
    long long x;
    bool color, v;
} N[MAXN + 2];

struct Edge {
    Node *s, *t;
    long long f, c;
    Edge *next, *r;

    Edge(Node *const s, Node *const t, const long long c) : s(s), t(t), f(0), c(c), next(s->e) {}
};

inline void addEdge(const int u, const int v, const long long c) {
    N[u].e = new Edge(&N[u], &N[v], c);
    N[v].e = new Edge(&N[v], &N[u], 0);
    (N[u].e->r = N[v].e)->r = N[u].e;
}

struct Dinic {
    bool makeLevelGraph(Node *const s, Node *const t, const int n) {
        for (int i = 0; i < n; i++) N[i].l = 0, N[i].c = N[i].e;

        std::queue<Node *> q;
        q.push(s);
        s->l = 1;

        while (!q.empty()) {
            Node *v = q.front();
            q.pop();

            for (Edge *e = v->e; e; e = e->next) {
                if (e->f < e->c && e->t->l == 0) {
                    e->t->l = v->l + 1;
                    if (e->t == t) return true;
                    else q.push(e->t);
                }
            }
        }

        return false;
    }

    long long findPath(Node *const s, Node *const t, const long long limit = LLONG_MAX) {
        if (s == t) return limit;

        for (Edge *&e = s->c; e; e = e->next) {
            if (e->f < e->c && e->t->l == s->l + 1) {
                long long flow = findPath(e->t, t, std::min(limit, e->c - e->f));
                if (flow > 0) {
                    e->f += flow;
                    e->r->f -= flow;
                    return flow;
                }
            }
        }

        return 0;
    }

    long long operator()(const int s, const int t, const int n) {
        long long res = 0;
        while (makeLevelGraph(&N[s], &N[t], n)) {
            long long flow;
            while ((flow = findPath(&N[s], &N[t])) > 0) res += flow;
        }

        return res;
    }
} dinic;

int n;
bool flag[MAXN][MAXN];

template <typename T> inline T sqr(const T x) { return x * x; }

template <typename T>
inline bool isSquare(const T x) {
    T t = static_cast<T>(sqrt(static_cast<double>(x)));
    return t * t == x;
}

template <typename T>
inline T gcd(const T a, const T b) {
    return !b ? a : gcd(b, a % b);
}

inline void color() {
    for (int i = 1; i <= n; i++) {
        if (N[i].v) continue;

        std::queue<Node *> q;
        q.push(&N[i]);
        N[i].color = true;
        N[i].v = true;

        while (!q.empty()) {
            Node *v = q.front();
            q.pop();

            for (Edge *e = v->e; e; e = e->next) {
                if (!e->t->v) {
                    e->t->v = true;
                    e->t->color = !v->color;
                    q.push(e->t);
                } else assert(e->t->color != v->color);
            }
        }
    }
}

inline void clean() {
    for (int i = 1; i <= n; i++) {
        Edge *next;
        for (Edge *&e = N[i].e; e; next = e->next, delete e, e = next);
    }
}

int main() {
    scanf("%d", &n);
    long long sum = 0;
    for (int i = 1; i <= n; i++) {
        scanf("%lld", &N[i].x);
        sum += N[i].x;
    }

    for (int i = 1; i <= n; i++) {
        for (int j = i + 1; j <= n; j++) {
            if (isSquare(sqr(N[i].x) + sqr(N[j].x)) && gcd(N[i].x, N[j].x) == 1) {
                flag[i][j] = flag[j][i] = true;
                addEdge(i, j, 0);
            }
        }
    }

    color();
    clean();

    const int s = 0, t = n + 1;
    for (int i = 1; i <= n; i++) {
        if (N[i].color) addEdge(s, i, N[i].x);
        else addEdge(i, t, N[i].x);

        for (int j = i + 1; j <= n; j++) {
            if (flag[i][j]) {
                if (N[i].color) addEdge(i, j, LLONG_MAX);
                else addEdge(j, i, LLONG_MAX);
            }
        }
    }

    long long maxFlow = dinic(s, t, n + 2);
    printf("%lld\n", sum - maxFlow);

    return 0;
}