题意

有nnn个数,其中同时满足下面两个条件的数对不能同时选,求选出一些数让和最大.

若两个数aaa,bbb同时满足以下条件，则aaa,bbb不能同时被选
- 存在正整数ccc，使a∗a+b∗b=c∗ca*a+b*b=c*ca∗a+b∗b=c∗c
- gcd(a,b)=1gcd(a,b)=1gcd(a,b)=1

分析

看到这熟悉二元关系,就能够用最小割做了.但是乍一看不是二分图的模型,就不能直接连了.所以有一种做法就是拆点.

但是我们看这两个式子可以推出来这的确是一个二分图,而且是奇偶二分图,证明如下:

a,ba,ba,b不可能同为偶数,否则不满足gcd(a,b)=1gcd(a,b)=1gcd(a,b)=1
a,ba,ba,b不可能同为奇数,证明为
- 假设存在a,ba,ba,b为奇数且c2=a2+b2c^2=a^2+b^2c2=a2+b2,那么ccc必为偶数,但是a2+b2≡2 (mod 4)a^2+b^2\equiv 2\ (mod\ 4)a2+b2≡2 (mod 4)而c2≡0 (mod 4)c^2\equiv 0\ (mod\ 4)c2≡0 (mod 4),矛盾

综上,存在矛盾的数对一定是奇偶性不同的数字,所以我们用二分图的方式,矛盾就连一条容量为∞\infty∞的边,然后SSS向奇数连容量为数值的边,偶数向TTT连容量为数值的边,最后用所有数的总和减去最小割就行了

CODE

#include <cstdio>

#include <cstring>

#include <vector>

#include <cmath>

#include <algorithm>

using namespace std;

typedef long long LL;

template<typename T>inline void read(T &num) {

    char ch; int flg=1;

    while((ch=getchar())<'0'||ch>'9')if(ch=='-')flg=-flg;

    for(num=0;ch>='0'&&ch<='9';num=num*10+ch-'0',ch=getchar());

    num*=flg;

}

const int inf = 1e9;

const int MAXN = 3005;

const int MAXM = 20005;

int n, m, fir[MAXN], S, T, cnt;

struct edge { int to, nxt; int c; }e[MAXM];

inline void add(int u, int v, int cc) {

    e[cnt] = (edge){ v, fir[u], cc }; fir[u] = cnt++;

    e[cnt] = (edge){ u, fir[v], 0 }; fir[v] = cnt++;

}

int dis[MAXN], vis[MAXN], info[MAXN], cur, q[MAXN];

inline bool bfs() {

    int head = 0, tail = 0;

    vis[S] = ++cur; q[tail++] = S;

    while(head < tail) {

        int u = q[head++];

        for(int i = fir[u]; ~i; i = e[i].nxt)

            if(e[i].c && vis[e[i].to] != cur)

                vis[e[i].to] = cur, dis[e[i].to] = dis[u] + 1, q[tail++] = e[i].to;

    }

    if(vis[T] == cur) memcpy(info, fir, (T+1)<<2);

    return vis[T] == cur;

}

int dfs(int u, int Max) {

    if(u == T || !Max) return Max;

    int flow=0, delta;

    for(int &i = info[u]; ~i; i = e[i].nxt)

        if(e[i].c && dis[e[i].to] == dis[u] + 1 && (delta=dfs(e[i].to, min(e[i].c, Max-flow)))) {

            e[i].c -= delta, e[i^1].c += delta, flow += delta;

            if(flow == Max) return flow;

        }

	if(!flow) dis[u] = -1;

    return flow;

}

inline int dinic() {

    memset(vis, 0, sizeof vis);

    int flow=0, x;

    while(bfs()) {

        while((x=dfs(S, inf))) flow+=x;

    }

    return flow;

}

int A[MAXN], sum;

int gcd(int x, int y) { return y ? gcd(y, x%y) : x; }

inline bool chk(int a,int b)

{

    int s = a*a + b*b, q = int(sqrt(s));

    if(q * q != s)return 0;

    if(gcd(a, b) != 1)return 0; //先判勾股数再判gcd会快好几倍

    return 1;

}

int main () {

    read(n); S = 0; T = n+1;

	memset(fir, -1, sizeof fir);

	for(int i = 1; i <= n; ++i) {

		read(A[i]); sum += A[i];

		if(A[i]&1) add(S, i, A[i]);

		else add(i, T, A[i]);

		for(int j = 1; j < i; ++j)

			if(chk(A[i], A[j])) {

				if(A[i]&1) add(i, j, inf);

				else add(j, i, inf);

			}

	}

	printf("%d\n", sum-dinic());

}

巴特西

BZOJ 3275: Number (二分图最小割)

题意

分析

CODE

最新文章

热门文章