【BZOJ3158】千钧一发

Description

Input

第一行一个正整数N。

第二行共包括N个正整数，第个正整数表示Ai。

第三行共包括N个正整数，第个正整数表示Bi。

Output

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

Sample Input

3 4 5 12

9 8 30 9

Sample Output

题解：一开始直接把那道题粘了下来交上去，结果发现并不一样~

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           using namespace std;int n,cnt,tot,ans,tx,ty;typedef long long ll;queue
           
             q;int A[1010],B[1010];int vx[1010],vy[1010],ex[1010],ey[1010],next[2000000],head[6010],to[2000000],val[2000000],d[6010];int gcd(int a,int b){ return (b==0)?a:gcd(b,a%b);}int dfs(int x,int mf){ if(x==n+1) return mf; int i,k,temp=mf; for(i=head[x];i!=-1;i=next[i]) { if(d[to[i]]==d[x]+1&&val[i]) { k=dfs(to[i],min(temp,val[i])); if(!k) d[to[i]]=0; val[i]-=k,val[i^1]+=k,temp-=k; if(!temp) break; } } return mf-temp;}int bfs(){ int i,u; memset(d,0,sizeof(d)); while(!q.empty()) q.pop(); q.push(0),d[0]=1; while(!q.empty()) { u=q.front(),q.pop(); for(i=head[u];i!=-1;i=next[i]) { if(!d[to[i]]&&val[i]) { d[to[i]]=d[u]+1; if(to[i]==n+1) return 1; q.push(to[i]); } } } return 0;}void add(int a,int b,int c){ to[cnt]=b; val[cnt]=c; next[cnt]=head[a]; head[a]=cnt++;}int main(){ scanf("%d",&n); int i,j,k,k1; memset(head,-1,sizeof(head)); for(i=1;i<=n;i++) scanf("%d",&A[i]); for(i=1;i<=n;i++) scanf("%d",&B[i]),tot+=B[i]; for(i=1;i<=n;i++) { if(A[i]&1) add(0,i,B[i]),add(i,0,0); else add(i,n+1,B[i]),add(n+1,i,0); } for(i=1;i<=n;i++) { for(j=1;j<=n;j++) { if(!(A[i]&1)||(A[j]&1)||gcd(A[i],A[j])>1) continue; ll k=(ll)A[i]*A[i]+(ll)A[j]*A[j]; if(ll(sqrt(k))*ll(sqrt(k))==k) { add(i,j,1<<30); add(j,i,0); } } } while(bfs()) ans+=dfs(0,1<<30); printf("%d",tot-ans); return 0;}