您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C++ >> 關於C++

BZOJ 3275：Number（數字選擇，最小割 / 網絡流）

編輯：關於C++

一、題目大意

有 n 個正整數，選擇若干數使和最大。限制：若 a,b 滿足 a²+b²=c² (c 為整數) 且 gcd(a,b)=1，則不能同時選。n ≤ 3000。

二、解題思路：最小割 / 最大權獨立集

構建圖：
- 源點 s、匯點 t
- 奇數點連邊 s→i 容量 a[i]
- 偶數點連邊容量 a[i]
- 若奇數 i 和偶數 j 不能共存，連邊 i→j 容量 INF
最小割即為需捨棄的最小權值和。答案 = 總和 - 最小割。
關鍵觀察：a²+b²=c² 且 gcd=1 ⇒ a,b 一奇一偶（畢達哥拉斯三元組性質）。故只需在奇偶之間連邊。

三、代碼實現（C++，Dinic）

#include <iostream>
#include <cstdio>
#include <cmath>
#include <queue>
#include <cstring>
using namespace std;

const int MAXN = 3100;
const int MAXM = 1000000;
const int INF = 1e9;

struct Edge { int to, next, cap; } e[MAXM];
int head[MAXN], cur[MAXN], dis[MAXN], a[MAXN];
int n, s, t, tot=1, ans=0;

void addEdge(int u, int v, int c) {
    e[++tot] = {v, head[u], c}; head[u] = tot;
    e[++tot] = {u, head[v], 0}; head[v] = tot;
}

bool bfs() {
    memset(dis, -1, sizeof(dis));
    queue q; q.push(s); dis[s] = 0;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int i = head[u]; i; i = e[i].next) {
            int v = e[i].to;
            if (e[i].cap && dis[v] == -1) {
                dis[v] = dis[u] + 1;
                q.push(v);
            }
        }
    }
    return dis[t] != -1;
}

int dfs(int u, int f) {
    if (u == t) return f;
    int flow = 0;
    for (int &i = cur[u]; i; i = e[i].next) {
        int v = e[i].to;
        if (e[i].cap && dis[v] == dis[u] + 1) {
            int pushed = dfs(v, min(f - flow, e[i].cap));
            e[i].cap -= pushed;
            e[i^1].cap += pushed;
            flow += pushed;
            if (flow == f) return flow;
        }
    }
    if (!flow) dis[u] = -1;
    return flow;
}

void dinic() {
    while (bfs()) {
        memcpy(cur, head, sizeof(head));
        ans += dfs(s, INF);
    }
}

bool check(int x, int y) {
    int sq = x*x + y*y;
    int r = (int)sqrt(sq);
    if (r*r != sq) return false;
    // gcd
    while (y) { int tmp = x%y; x=y; y=tmp; }
    return x == 1;
}

int main() {
    n = 0; // 讀入 n
    // 讀入 a[1..n]
    // 計算總和
    s = n+1; t = n+2;
    for (int i=1; i<=n; ++i) {
        if (a[i] & 1) addEdge(s, i, a[i]);
        else addEdge(i, t, a[i]);
    }
    for (int i=1; i<=n; ++i)
        for (int j=1; j<=n; ++j)
            if ((a[i]&1) && !(a[j]&1) && check(a[i], a[j]))
                addEdge(i, j, INF);
    dinic();
    printf("%d\n", total_sum - ans);
    return 0;
}