bzoj3158千钧一发-526互联

大豆说过：最大权独立集你就会个二分图，你又不会一般图，往二分图上想。

先看第二个条件：不互质的数可以连边。所以现在只剩下互质的数了。

然后看第一个条件（再联想到大豆说的：二分图先想奇偶性）：互质的数只存在：奇数和偶数；奇数和奇数。

两个奇数肯定能表示成如下形式：\(2 \cdot a + 1\) 和 \(2 \cdot b + 1\)

则他俩的平方和为 \(4a^2 + 4b^2 + 4a + 4b + 2\)

显然表示成了 \(4x + 2\) 一定不是某个整数的平方。

所以只剩奇数和偶数的情况了。直接二分图跑最小割就行了。

#include <bits/stdc++.h>

int N, S = 1, T = 2;
int tot = 2, id[1100];
long long A[1100], B[1100], answer;
int cnt = 1, head[1100], next[2100000], to[2100000];
long long value[2100000];

void AddEdge(int u, int v, long long val) {
    ++ cnt;
    next[cnt] = head[u];
    head[u] = cnt;
    to[cnt] = v;
    value[cnt] = val;
}

namespace Dinic {
    int deep[1100], cur[1100];
    void clear() {
        for (int i = 1; i <= tot; ++ i) {
            deep[i] = 0;
            cur[i] = head[i];
        }
    }
    bool Bfs(int begin, int end) {
        clear();
        deep[begin] = 1;
        std::queue<int> queue;
        queue.emplace(begin);
        while (queue.size()) {
            int now = queue.front();
            queue.pop();
            for (int i = head[now]; i; i = next[i]) {
                if (!value[i] || deep[to[i]])
                    continue;
                deep[to[i]] = deep[now] + 1;
                if (to[i] == end)
                    return true;
                queue.emplace(to[i]);
            }
        }
        return false;
    }
    long long Dfs(int now, int end, long long flow) {
        if (now == end)
            return flow;
        long long rest = flow, temp;
        for (int i = cur[now]; i && rest; i = next[i]) {
            cur[now] = i;
            if (value[i] && deep[to[i]] == deep[now] + 1) {
                temp = Dfs(to[i], end, std::min(rest, value[i]));
                if (!temp)
                    deep[to[i]] = 0;
                value[i] -= temp;
                value[i ^ 1] += temp;
                rest -= temp;
            }
        }
        return flow - rest;
    }
}

bool check(long long a1, long long a2) {
    long long A1 = a1 * a1, A2 = a2 * a2;
    return (std::sqrt(1.0 * A1 + 1.0 * A2) == (int)std::sqrt(1.0 * A1 + 1.0 * A2));
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);

    std::cin >> N;
    for (int i = 1; i <= N; ++ i)  {
        std::cin >> A[i];
        id[i] = ++ tot;
    }
    for (int i = 1; i <= N; ++ i) {
        std::cin >> B[i];
        answer += B[i];
        if (A[i] % 2 == 1) {
            AddEdge(S, id[i], B[i]);
            AddEdge(id[i], S, 0);
        }
        else {
            AddEdge(id[i], T, B[i]);
            AddEdge(T, id[i], 0);
        }
    }
    for (int i = 1; i <= N; ++ i) {
        for (int j = 1; j <= N; ++ j) {
            if (i == j || std::__gcd(A[i], A[j]) != 1 || !check(A[i], A[j]))
                continue;
            int flag[2] = {0, 0};
            flag[A[i] % 2] = id[i];
            flag[A[j] % 2] = id[j];
            if (flag[0] && flag[1]) {
                AddEdge(flag[1], flag[0], 1000000000000000000);
                AddEdge(flag[0], flag[1], 0);
            }
        }
    }
    while (Dinic::Bfs(S, T))
        answer -= Dinic::Dfs(S, T, 1e18);
    std::cout << answer << '\n';
    return 0;
}