BZOJ3158 千钧一发 <黑白染色+最小割>

Problem

千钧一发

$\mathrm{Time\;Limit:\;10\;Sec}$
$\mathrm{Memory\;Limit:\;512\;MB}$

Description

![][1]

Input

第一行一个正整数$N$。
第二行共包括$N$个正整数，第 个正整数表示$A_i$。
第三行共包括$N$个正整数，第 个正整数表示$B_i$。

Output

共一行，包括一个正整数，表示在合法的选择条件下，可以获得的能量值总和的最大值。

Sample Input

4
3 4 5 12
9 8 30 9

Sample Output

39

HINT

$1\le N\le 1000,1\le A_i,B_i\le 10^6$

标签：黑白染色 最小割

Solution

和BZOJ3275差不多
两条性质：

• $奇^2+奇^2 \ne X^2 (X\in \mathbb{N}^*)$
• $\gcd(偶,偶) \ne 1$

$\therefore$奇与奇共存，偶与偶共存
建模：$S\to 奇, cap=b[i]$，$偶\to T, cap=b[i]$，$奇\to 偶, cap=\infty$
$ans = 总权值-最小割$
注意判断是否能组成勾股数时平方要开long long。

Code

#include <bits/stdc++.h>
#define MAX_N 1000
#define INF 2147483647
using namespace std;
int n, s, t, sum, cnt, a[MAX_N+5], b[MAX_N+5], d[MAX_N+5], pr[MAX_N+5];
struct node {int u, v, c, nxt;} E[MAX_N*1000];
int gcd(int x, int y) {return y ? gcd(y, x%y) : x;}
void init() {s = 0, t = n+1; memset(pr, -1, sizeof pr);}
void insert(int u, int v, int c) {E[cnt].v = v, E[cnt].c = c, E[cnt].nxt = pr[u], pr[u] = cnt++;}
void addedge(int u, int v, int c) {insert(u, v, c), insert(v, u, 0);}
bool BFS() {
    queue <int> que;	que.push(s);
    memset(d, -1, sizeof d), d[s] = 0;
    while (!que.empty()) {
        int u = que.front();	que.pop();
        for (int i = pr[u]; ~i; i = E[i].nxt) {
            int v = E[i].v, c = E[i].c;
            if (!c || ~d[v])	continue;
            d[v] = d[u]+1, que.push(v);
        }
    }
    return ~d[t];
}
int DFS(int u, int flow) {
    if (u == t)	return flow;
    int ret = 0;
    for (int i = pr[u]; ~i; i = E[i].nxt) {
        int v = E[i].v, c = E[i].c;
        if (!c || d[v] != d[u]+1)	continue;
        int tmp = DFS(v, min(flow, c));
        E[i].c -= tmp, E[i^1].c += tmp;
        flow -= tmp, ret += tmp;
        if (!flow)	break;
    }
    if (!ret) d[u] = -1;
    return ret;
}
int Dinic() {int ret = 0;    while (BFS()) ret += DFS(s, INF);	return ret;}
bool chk(int i, int j) {return gcd(a[i], a[j]) == 1 && sqrt(1LL*a[i]*a[i]+1LL*a[j]*a[j]) == floor(sqrt(1LL*a[i]*a[i]+1LL*a[j]*a[j]));}
int main() {
    scanf("%d", &n), init();
    for (int i = 1; i <= n; i++) scanf("%d", a+i);
    for (int i = 1; i <= n; i++) scanf("%d", b+i), sum += b[i];
    for (int i = 1; i <= n; i++)
        if (a[i]%2) addedge(s, i, b[i]);
        else addedge(i, t, b[i]);
    for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++)
        if (a[i]%2 == 1 && a[j]%2 == 0 && chk(i, j)) addedge(i, j, INF);
    return printf("%d", sum-Dinic()), 0;
}