BZOJ 3158 千钧一发

大力猜一顿结论：

如果两个数$i$和$j$，满足$a_i$和$a_j$均不满足题目里给定的两个条件，就在$i$和$j$之间连接一条边，那么形成的图一定是一张二分图。

暴力跑一下跑到$1000$都是成立的，再大的没法跑了。

然后原题转化为二分图的最大带权独立集，最小割即可。

// luogu-judger-enable-o2
#include <assert.h>
#include <algorithm>
#include <cmath>
#include <iostream>
#include <queue>
#include <vector>

using int_t = long long int;
using std::cin;
using std::cout;
using std::endl;

const int_t LARGE = 1010;
const int_t SOURCE = 1001;
const int_t SINK = 1002;
const int_t INF = 0x7fffffffffffff;
struct Edge {
    int_t to, capacity, flow;
    Edge* rev;
};

std::vector<Edge*> graph[LARGE + 1];
std::vector<int_t> graph0[LARGE + 1];
int_t dis[LARGE + 1], curr[LARGE + 1], visited[LARGE + 1], color[LARGE + 1];
//压入边(from,to,lower,upper),返回正向边
Edge* pushEdge(int_t from, int_t to, int_t cap) {
    Edge* edge0 = new Edge{to, cap, 0};
    Edge* edge1 = new Edge{from, 0, 0, edge0};
    edge0->rev = edge1;
    graph[from].push_back(edge0);
    graph[to].push_back(edge1);
#ifdef DEBUG
    cout << "Edge " << from << "," << to << " cap " << cap << endl;
#endif
    return edge0;
}
bool BFS(int_t source, int_t sink) {
    std::fill(dis, dis + 1 + LARGE, INF);
    std::fill(curr, curr + 1 + LARGE, 0);
    std::fill(visited, visited + 1 + LARGE, false);
    std::queue<int_t> queue;
    dis[source] = 0;
    visited[source] = true;
    queue.push(source);
    while (queue.empty() == false) {
        int_t front = queue.front();
        queue.pop();
        for (Edge* edge : graph[front]) {
            if (edge->capacity > edge->flow && visited[edge->to] == false) {
                visited[edge->to] = true;
                dis[edge->to] = dis[front] + 1;
                queue.push(edge->to);
            }
        }
    }
    return visited[sink];
}
int_t DFS(int_t vtx, int_t sink, int_t minf = INF) {
    if (vtx == sink || minf == 0) return minf;
    int_t result = 0;
    for (int_t& i = curr[vtx]; i < graph[vtx].size(); i++) {
        Edge* edge = graph[vtx][i];
        if (dis[edge->to] == dis[vtx] + 1) {
            int_t x = DFS(edge->to, sink,
                          std::min(minf, edge->capacity - edge->flow));
            if (x > 0) {
                minf -= x;
                result += x;
                edge->flow += x;
                edge->rev->flow -= x;
                if (minf == 0) break;
            }
        }
    }
    return result;
}
int_t number[LARGE + 1], value[LARGE + 1];
int_t gcd(int_t a, int_t b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}
bool DFS(int_t vtx) {
    if (color[vtx] == 0) color[vtx] = 1;
    for (int_t to : graph0[vtx]) {
        if (color[to] + color[vtx] != 3) {
            if (color[to] == 0) {
                color[to] = 3 - color[vtx];
            } else if (color[to] == color[vtx])
                return false;
            if (DFS(vtx) == false) return false;
        }
    }
    return true;
}
int main() {
    int_t n;
    cin >> n;
    for (int_t i = 1; i <= n; i++) cin >> number[i];
    for (int_t i = 1; i <= n; i++) cin >> value[i];
    for (int_t i = 1; i <= n; i++) {
        for (int_t j = i + 1; j <= n; j++) {
            const auto check = [&](int_t a, int_t b) -> bool {
                int_t x = sqrtl(a * a + b * b);
                return (x * x == a * a + b * b) && gcd(a, b) == 1;
            };
            if (check(number[i], number[j])) {
                graph0[i].push_back(j);
                graph0[j].push_back(i);
            }
        }
    }
    for (int_t i = 1; i <= n; i++) {
        if (color[i] == 0) {
            if (DFS(i) == false) {
                assert(false);
            }
        }
    }
    int_t result = 0;
    for (int_t i = 1; i <= n; i++) {
        if (color[i] == 1) {
            pushEdge(SOURCE, i, value[i]);
            for (int_t to : graph0[i]) {
                if (color[to] == 2) {
                    pushEdge(i, to, INF);
                }
            }
        } else {
            pushEdge(i, SINK, value[i]);
        }
#ifdef DEBUG
        cout << "color " << i << " = " << color[i] << endl;
#endif
        result += value[i];
    }
    while (BFS(SOURCE, SINK)) result -= DFS(SOURCE, SINK);
    cout << result << endl;
    return 0;
}