网络流/最小割

---

　　这题跟限制条件是一样的= =所以可以用相同的方法去做……只要把边的容量从a[i]改成b[i]就行了～

（果然不加当前弧优化要略快一点）

1 /**************************************************************  2     Problem: 3158  3     User: Tunix  4     Language: C++  5     Result: Accepted  6     Time:196 ms  7     Memory:13028 kb  8 ****************************************************************/  9   10 //BZOJ 3158 11 #include
      
        12 #include
       
         13 #include
        
          14 #include
         
           15 #include
          
            16 #include
           
             17 #include
            
              18 #define rep(i,n) for(int i=0;i
             
              =n;--i) 21 #define pb push_back 22 using namespace std; 23 inline int getint(){ 24 int v=0,sign=1; char ch=getchar(); 25 while(ch<'0'||ch>'9'){ if (ch=='-') sign=-1; ch=getchar();} 26 while(ch>='0'&&ch<='9'){ v=v*10+ch-'0'; ch=getchar();} 27 return v*sign; 28 } 29 const int N=1100,M=1000000,INF=~0u>>2; 30 typedef long long LL; 31 /******************tamplate*********************/ 32 int n,m,tot,ans,a[N],b[N]; 33 struct edge{ int to,v;}; 34 int gcd(int a,int b){ return b ? gcd(b,a%b) : a;} 35 bool judge(LL a,LL b){ 36 LL s=a*a+b*b; 37 LL q=sqrt(s); 38 if (q*q!=s) return 0; 39 if (gcd(a,b)!=1) return 0; 40 return 1; 41 } 42 struct Net{ 43 edge E[M]; 44 int head[N],next[M],cnt; 45 void ins(int x,int y,int v){ 46 E[++cnt]=(edge){y,v}; 47 next[cnt]=head[x]; head[x]=cnt; 48 } 49 void add(int x,int y,int v){ 50 ins(x,y,v); ins(y,x,0); 51 } 52 int s,t,d[N],Q[N]; 53 void init(){ 54 n=getint(); cnt=1; 55 tot=ans=0; 56 s=0; t=n+1; 57 F(i,1,n) a[i]=getint(); 58 F(i,1,n){ 59 b[i]=getint();tot+=b[i]; 60 if (a[i]&1) add(s,i,b[i]); 61 else add(i,t,b[i]); 62 } 63 F(i,1,n) if (a[i]&1) 64 F(j,1,n) if((a[j]&1)==0) 65 if (judge(a[i],a[j])) add(i,j,INF); 66 } 67 bool mklevel(){ 68 memset(d,-1,sizeof d); 69 d[s]=0; 70 int l=0,r=-1; 71 Q[++r]=s; 72 while(l<=r){ 73 int x=Q[l++]; 74 for(int i=head[x];i;i=next[i]) 75 if (d[E[i].to]==-1 && E[i].v){ 76 d[E[i].to]=d[x]+1; 77 Q[++r]=E[i].to; 78 } 79 } 80 return d[t]!=-1; 81 } 82 int dfs(int x,int a){ 83 if (x==t) return a; 84 int flow=0; 85 for(int i=head[x];i && flow
             
            
           
          
         
        
       
      

 

3158: 千钧一发

Time Limit: 10 Sec  Memory Limit: 512 MB

Submit: 590  Solved: 225

[ ][ ][ ]

Description

 

Input

第一行一个正整数N。

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

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

Output

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

Sample Input

4

3 4 5 12

9 8 30 9

Sample Output

39

HINT

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

Source

[ ][ ][ ]