【BZOJ】【3158】千钧一发
网络流/最小割这题跟BZOJ 3275限制条件是一样的= =所以可以用相同的方法去做……只要把边的容量从a改成b就行了～（果然不加当前弧优化要略快一点）
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,b;
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;
44 int head,next,cnt;
45 void ins(int x,int y,int v){
46 E[++cnt]=(edge){y,v};
47 next=head; head=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,Q;
53 void init(){
54 n=getint(); cnt=1;
55 tot=ans=0;
56 s=0; t=n+1;
57 F(i,1,n) a=getint();
58 F(i,1,n){
59 b=getint();tot+=b;
60 if (a&1) add(s,i,b);
61 else add(i,t,b);
62 }
63 F(i,1,n) if (a&1)
64 F(j,1,n) if((a&1)==0)
65 if (judge(a,a)) add(i,j,INF);
66 }
67 bool mklevel(){
68 memset(d,-1,sizeof d);
69 d=0;
70 int l=0,r=-1;
71 Q[++r]=s;
72 while(l<=r){
73 int x=Q;
74 for(int i=head;i;i=next)
75 if (d.to]==-1 && E.v){
76 d.to]=d+1;
77 Q[++r]=E.to;
78 }
79 }
80 return d!=-1;
81 }
82 int dfs(int x,int a){
83 if (x==t) return a;
84 int flow=0;
85 for(int i=head;i && flow<a;i=next)
86 if (E.v && d.to]==d+1){
87 int f=dfs(E.to,min(a-flow,E.v));
88 E.v-=f;
89 E.v+=f;
90 flow+=f;
91 }
92 if (!flow) d=-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
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
文档来源：51CTO技术博客https://blog.51cto.com/u_15320872/3267121
页:
[1]