[BZOJ3275]Number 二分图最大点独立集


原题链接
有N个正整数,需要从中选出一些数,使这些数的和最大。
若两个数a,b同时满足以下条件,则a,b不能同时被选
1:存在正整数C,使a*a+b*b=c*c
2:gcd(a,b)=1

以后用换行代替句号假装hzwer和PoPoQQQ写题解(逃

挺神的一道题
连边后发现是一个图的最大点独立集
然而这是个NP问题,所以很大可能是二分图
下面证明它是个二分图
首先对于任意两个偶数a,b,有gcd(a,b)!=1,不满足条件2
因此偶数之间肯定没有边
那么是不是奇数之间也不可能有边呢
只需证明两个奇数不可能满足条件1
假设存在奇数a,b满足存在一个符合a^2+b^2=c^2的整数c
首先c不可能是奇数,因为显然c^2是偶数
c是偶数也不行,因为显然c^2不能是4的倍数
因此不存在c,也即奇数a,b不可能满足a^2+b^2=c^2
所以奇数之间也不能有边
因此整个图分成了奇数和偶数两部分,两部分内部都没有边,是二分图
跑最小割即可

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm> 
#define N 6666
#define M 6666666
using namespace std;
typedef long long ll;
inline ll gcd(ll x,ll y)
{
    ll t;
    while(y)t=x,x=y,y=t%y;
    return x;
}
inline bool check(ll x,ll y)
{
    ll t=x*x+y*y,k=sqrt(t+0.1);
    return k*k==t;  
}
const ll inf=0x3bbbbbbbbbbbbbll;
int n,head[N],to[M],nxt[M],tot=1;
ll f[M];
inline void add(int x,int y,ll z)
{
    to[++tot]=y,nxt[tot]=head[x],head[x]=tot,f[tot]=z;
    to[++tot]=x,nxt[tot]=head[y],head[y]=tot,f[tot]=0;
}
int s,t;
ll a[N],ans;
int q[N],l,r,dis[N];
inline bool bfs()
{
    memset(dis,-1,sizeof dis);
    l=1,r=0;
    dis[s]=0,q[++r]=s;
    int x,i,y;
    while(l<=r)
    {
        x=q[l++];
        for(i=head[x];i;i=nxt[i])if(f[i]>0&&dis[y=to[i]]<0)
        {
            dis[y]=dis[x]+1;
            if(y==t)return 1;
            q[++r]=y;
        }
    }
    return 0;
}
ll dinic(int x,ll flow)
{
    if(x==t)return flow;
    int i;
    ll lft=flow,tmp;
    for(i=head[x];i;i=nxt[i])if(dis[to[i]]==dis[x]+1&&f[i]>0)
    {
        tmp=dinic(to[i],min(lft,f[i]));
        if(!tmp)dis[to[i]]=-1;
        lft-=tmp,f[i]-=tmp,f[i^1]+=tmp;
        if(!lft)return flow;
    }
    return flow-lft;
}
ll maxflow()
{
    ll re=0;
    while(bfs())re+=dinic(s,inf);
    return re;
}
int main()
{
    cin>>n;
    s=n+1,t=n+2;
    int i,j;
    for(i=1;i<=n;++i)
    {
        scanf("%lld",&a[i]);
        if(a[i]&1)add(s,i,a[i]);
        else add(i,t,a[i]); 
        ans+=a[i];
    }
    for(i=1;i<=n;++i)if(a[i]&1)
    {
        for(j=1;j<=n;++j)if(!(a[j]&1)&&gcd(a[i],a[j])==1&&check(a[i],a[j]))add(i,j,inf);
    }
    cout<<ans-maxflow();
    return 0;
} 
/*
10
126578 542218 398981 4878751 135484 976362 210540 457110 6578187 103642
14407853
*/

发表评论

电子邮件地址不会被公开。 必填项已用*标注