就行了~
(果然不加当前弧优化要略快一点)
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<cmath>
12 #include<vector>
13 #include<cstdio>
14 #include<cstring>
15 #include<cstdlib>
16 #include<iostream>
17 #include<algorithm>
18 #define rep(i,n) for(int i=0;i<n;++i)
19 #define F(i,j,n) for(int i=j;i<=n;++i)
20 #define D(i,j,n) for(int i=j;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<a;i=next[i])
86 if (E[i].v && d[E[i].to]==d[x]+1){
87 int f=dfs(E[i].to,min(a-flow,E[i].v));
88 E[i].v-=f;
89 E[i^1].v+=f;
90 flow+=f;
91 }
92 if (!flow) d[x]=-1;
93 return flow;
94 }
95 void Dinic(){
96 while(mklevel())
97 ans+=dfs(s,INF);
98 }
99 }G1;
100
101 int main(){
102 #ifndef ONLINE_JUDGE
103 freopen("3158.in","r",stdin);
104 freopen("3158.out","w",stdout);
105 #endif
106 G1.init(); G1.Dinic();
107 printf("%d\n",tot-ans);
108 return 0;
109 }
View Code
3158: 千钧一发
Time Limit: 10 Sec Memory Limit: 512 MB
Submit: 590 Solved: 225
[Submit][Status][Discuss]
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
Katharon+#1
[Submit][Status][Discuss]