BZOJ3275Number——二分图最大权独立集

迈不过友情╰ 2022-01-05 15:11 236阅读 0赞

## 题目描述 ##

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

## 输入 ##

第一行一个正整数n，表示数的个数。n<=3000

第二行n个正整数a1,a2,...an

## 输出 ##

最大的和

## 样例输入 ##

5  
3 4 5 6 7

## 样例输出 ##

可以发现如果两个数都是偶数，那么$gcd>=2$，一定可以同时选；如果两个数都是奇数，那么两个数的平方和是$4$的倍数加$2$，而一个奇数的平方是$4$的倍数加$1$，一个偶数的平方是$4$的倍数，所以两个奇数一定可以同时选。那么我们可以将奇数与源点相连，将偶数与汇点相连，然后枚举任意一对奇偶不同的数，如果不能同时选就在两点之间连边。答案就是所有数之和$-$最小割。

#include<set>
    #include<map>
    #include<queue>
    #include<stack>
    #include<cmath>
    #include<cstdio>
    #include<vector>
    #include<bitset>
    #include<cstring>
    #include<iostream>
    #include<algorithm>
    #define INF 0x3f3f3f3f
    #define ll long long
    using namespace std;
    int head[4000];
    int to[3000000];
    int next[3000000];
    int val[3000000];
    int d[4000];
    int q[4000];
    int back[4000];
    int S,T;
    int x,y,k;
    int n,m;
    int tot=1;
    int ans;
    int a[4000];
    void add(int x,int y,int v)
    {
        tot++;
        next[tot]=back[x];
        back[x]=tot;
        to[tot]=y;
        val[tot]=v;
        tot++;
        next[tot]=back[y];
        back[y]=tot;
        to[tot]=x;
        val[tot]=0;
    } 
    bool bfs(int S,int T)
    {
        int r=0;
        int l=0;
        memset(d,-1,sizeof(d));
        q[r++]=T;
        d[T]=2;
        while(l<r)
        {
            int now=q[l];
            for(int i=back[now];i;i=next[i])
            {
                if(d[to[i]]==-1&&val[i^1]!=0)
                {
                    d[to[i]]=d[now]+1;
                    q[r++]=to[i];
                }
            }
            l++;
        }
        if(d[S]==-1)
        {
            return false;
        }
        else
        {
            return true;
        }
    }
    int dfs(int x,int flow)
    {
        if(x==T)
        {
            return flow;
        }
        int now_flow;
        int used=0;
        for(int &i=head[x];i;i=next[i])
        {
            if(d[to[i]]==d[x]-1&&val[i]!=0)
            {
                now_flow=dfs(to[i],min(flow-used,val[i]));
                val[i]-=now_flow;
                val[i^1]+=now_flow;
                used+=now_flow;
                if(now_flow==flow)
                {
                    return flow;
                }
            }
        }
        if(used==0)
        {
            d[x]=-1;
        }
        return used;
    }
    int dinic()
    {
        int res=0;
        while(bfs(S,T))
        {
            memcpy(head,back,sizeof(back));
            res+=dfs(S,0x3f3f3f3f);
        }
        return res;
    }
    int gcd(int x,int y)
    {
        return y==0?x:gcd(y,x%y);
    }
    ll get(ll x)
    {
        return 1ll*x*x;
    }
    bool check(int x,int y)
    {
        if(gcd(x,y)!=1)
        {
            return false;
        }
        ll c=1ll*x*x+1ll*y*y;
        if(get(sqrt(c))!=c)
        {
            return false;
        }
        return true;
    }
    int main()
    {
        scanf("%d",&n);
        S=n+1;
        T=S+1;
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
            ans+=a[i];
            if(a[i]&1)
            {
                add(S,i,a[i]);
            }
            else
            {
                add(i,T,a[i]);
            }
        }
        for(int i=1;i<=n;i++)
        {
            for(int j=i+1;j<=n;j++)
            {
                if(check(a[i],a[j]))
                {
                    if(a[i]&1)
                    {
                        add(i,j,INF);
                    }
                    else
                    {
                        add(j,i,INF);
                    }
                }
            }
        }
        printf("%d",ans-dinic());
    }

转载于:https://www.cnblogs.com/Khada-Jhin/p/10583853.html