BZOJ3518: a close call

Description


Input

The first line is a positive integer N.

The second line contains N positive integers, and the first positive integer represents Ai.

The third row contains N positive integers, and the positive integer represents Bi.

Output

A total of one line, including a positive integer, represents the maximum value of the sum of energy values that can be obtained under legal selection conditions.

Sample Input

4
3 4 5 12
9 8 30 9

Sample Output

39

HINT

1<=N<=1000,1<=Ai,Bi<=10^6

Title gate

At first, I thought I had to use mathematical methods to get the DP equation stuck for half a day, and I felt like I was mentally retarded
After thinking about it for a long time, it seems to be the most powerful closed graph??

First of all, we can make it clear that we can't cooperate with each other to put a piece of energy, but what about next??
After another 20 minutes of thinking, I suddenly remembered that when I was taking the exam, there was a question that could be solved by the parity of numbers
Isn't this the same question?
Two even numbers, they have at least two common factors
There must be no Pythagorean between two odd numbers at right angles

And then odd numbers on one side, even numbers on the other side
There are two points to note:
1. When a [i] is square, it will explode int
2. It is not allowed to connect odd and even sides

Get rid of me for nearly an hour

The code is as follows:

#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
using namespace std;
typedef long long ll;
const ll INF=1e7;
struct node
{
    int x,y,next,other;
    ll c;
}a[2100000];int len,last[2100000];
void ins(int x,int y,ll c)
{
    int k1,k2;
    k1=++len;
    a[len].x=x;a[len].y=y;a[len].c=c;
    a[len].next=last[x];last[x]=len;

    k2=++len;
    a[len].x=y;a[len].y=x;a[len].c=0;
    a[len].next=last[y];last[y]=len;

    a[k1].other=k2;
    a[k2].other=k1;
}
int head,tail,h[3100000];
int st,ed,list[2100000];
bool bt_h()
{
    memset(h,0,sizeof(h));h[st]=1;
    list[1]=st;head=1;tail=2;
    while(head<tail)
    {
        int x=list[head];
        for(int k=last[x];k;k=a[k].next)
        {
            int y=a[k].y;
            if(h[y]==0&&a[k].c>0)
            {
                h[y]=h[x]+1;
                list[tail++]=y;
            }
        }
        head++;
    }
    if(h[ed]>0)return true;
    return false;
}
int findflow(int x,ll f)
{
    if(x==ed)return f;
    ll s=0,t;
    for(int k=last[x];k;k=a[k].next)
    {
        int y=a[k].y;
        if(h[y]==h[x]+1&&a[k].c>0&&s<f)
        {
            s+=(t=findflow(y,min(a[k].c,f-s)));
            a[k].c-=t;a[a[k].other].c+=t;
        }
    }
    if(s==0)h[x]=0;
    return s;

}
int n;
ll A[1100],b[1100];
int gcd(ll a,ll b)
{
    if(a==0)return b;
    return gcd(b%a,a);
}
int main()
{
    ll sum=0;
    scanf("%d",&n);
    st=0;ed=n+1;
    len=0;memset(last,0,sizeof(last));
    for(int i=1;i<=n;i++)scanf("%lld",&A[i]);
    for(int i=1;i<=n;i++)scanf("%lld",&b[i]),sum+=b[i];
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
        {
            if(i!=j&&A[i]%2==1&&A[j]%2==0)
            {
                double x;
                x=sqrt((ll)A[i]*A[i]+(ll)A[j]*A[j]);
                if(x==floor(x)&&gcd(A[i],A[j])==1)
                    ins(i,j,INF);
            }
        }
    for(int i=1;i<=n;i++)
    {
        if(A[i]%2==0)ins(i,ed,b[i]);
        else ins(st,i,b[i]);
    }
    ll ans=0;
    while(bt_h()==true)
        ans+=findflow(st,INF);
    printf("%lld\n",sum-ans);
    return 0;
}

by_lmy

Posted on Mon, 04 May 2020 23:26:54 -0700 by BlueKai