http://www.lydsy.com/JudgeOnline/problem.php?id=2661

Ideas : Preprocess each number , And then, if there is x^2=y^2+z^2 And z And y Coprime ,

s->x 1 ,0

x+n-> t 1 , 0

x->y+n -> 1 , inf-x-y

y->x+n-> 1 ,inf-x-y

 #include<algorithm>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<iostream>
#define inf 1000000
int l,r,pd[],L[],R[],cnt,sz,b[];
int tot,go[],next[],first[],cost[],flow[];
int op[],dis[],c[],vis[],edge[],from[];
int S,T,ans1,ans2;
int gcd(int a,int b){if (b==) return a;else return gcd(b,a%b);}
int read(){
char ch=getchar();int t=,f=;
while (ch<''||ch>''){if (ch=='-') f=-;ch=getchar();}
while (''<=ch&&ch<=''){t=t*+ch-'';ch=getchar();}
return t*f;
}
void insert(int x,int y,int z,int l){
tot++;
go[tot]=y;
next[tot]=first[x];
first[x]=tot;
flow[tot]=z;
cost[tot]=l;
}
void add(int x,int y,int z,int l){
insert(x,y,z,l);op[tot]=tot+;
insert(y,x,,-l);op[tot]=tot-;
}
bool spfa(){
for (int i=;i<=T;i++)
dis[i]=inf,vis[i]=;
int h=,t=;c[]=S;vis[S]=;dis[S]=;
while (h<=t){
int now=c[h++];
for (int i=first[now];i;i=next[i]){
int pur=go[i];
if (dis[pur]>dis[now]+cost[i]&&flow[i]){
dis[pur]=dis[now]+cost[i];
edge[pur]=i;
from[pur]=now;
if (vis[pur]) continue;
vis[pur]=;
c[++t]=pur;
}
}
vis[now]=;
}
return dis[T]!=inf;
}
void updata(){
int mn=0x3f3f3f3f;
for (int i=T;i!=S;i=from[i]){
mn=std::min(mn,flow[edge[i]]);
}
for (int i=T;i!=S;i=from[i]){
ans2+=mn*cost[edge[i]];
flow[edge[i]]-=mn;
flow[op[edge[i]]]+=mn;
}
ans1+=mn;
}
int main(){
l=read();r=read();
if (l>r) std::swap(l,r);
for (int i=;i<=;i++) pd[i*i]=i;
for (int j=l;j<=r;j++)
for (int i=j+;i<=r;i++){
int k=i*i-j*j;
if (pd[k]&&gcd(pd[k],j)==){
b[i]=b[j]=;
cnt++;
L[cnt]=j;
R[cnt]=i;
}
}
for (int i=l;i<=r;i++)
if (b[i])
b[i]=++sz;
S=;T=sz+sz+;
for (int i=l;i<=r;i++)
if (b[i])
add(S,b[i],,),add(b[i]+sz,T,,);
for (int i=;i<=cnt;i++){
add(b[L[i]],b[R[i]]+sz,,inf-L[i]-R[i]);
add(b[R[i]],b[L[i]]+sz,,inf-L[i]-R[i]);
}
while (spfa()) updata();
printf("%d ",ans1/);
printf("%d\n",(ans1*inf-ans2)/);
}

BZOJ 2661 Read more related articles

  1. BZOJ 2661 Repeatedly read ( Cost stream )

    Topic link :http://61.187.179.132/JudgeOnline/problem.php?id=2661 The question : Give an interval [a,b] All integers in , If two of them x,y( set up x>y) ...

  2. BZOJ 2661: [BeiJing wc2012] Repeatedly read Cost stream

    2661: [BeiJing wc2012] Repeatedly read Description There will always be such an elimination game in the IQ test . But now I'm facing a lot of problems QQ The eye testing game in the game . Our rule is , Give a closed ...

  3. bzoj 2661: [BeiJing wc2012] Repeatedly read

    #include<cstdio> #include<iostream> #include<cstring> #include<cmath> #inclu ...

  4. 【BZOJ】【2661】【Beijing WC2012】 Repeatedly read

    Network flow / Cost stream / Maximum weight matching of bipartite graphs Split point cost flow for maximum weight matching …… Why do I take zyf and Hzwer I can't hand in my code ……WA So many times ……so sad Ask for the guidance of the passing God cow >_< Thank you very much //BZOJ ...

  5. 2661: [BeiJing wc2012] Repeatedly read

    Description There will always be such an elimination game in the IQ test . But now I'm facing a lot of problems QQ The eye testing game in the game . Our rule is , Give a closed interval [a,b] All integers in , If two of them x,y( ...

  6. BZOJ2661: [BeiJing wc2012] Repeatedly read

    2661: [BeiJing wc2012] Repeatedly read Time Limit: 10 Sec  Memory Limit: 128 MBSubmit: 483  Solved: 200[Submit][S ...

  7. BZOJ ac100 Question archiving

    Before you know it AC100 Title , It seems to be all about water . Make an archive here ( Thank you very much, especially cloud God http://hi.baidu.com/greencloud And sister Lijie http://wjmzbmr.com/ ...

  8. [BZOJ2661][BeiJing wc2012] Repeatedly read Cost stream

    2661: [BeiJing wc2012] Repeatedly read Time Limit: 10 Sec  Memory Limit: 128 MBSubmit: 1349  Solved: 577[Submit][ ...

  9. bzoj AC In reverse order

    Search GO explain : Enter the question number to enter the corresponding question directly , To search for topics with numbers , Please put a single quotation mark before the key words Problem ID Title Source AC Submit Y 1000 A+B Problem ...

Random recommendation

  1. 【 Small white CFD The journey 】04 Mission

    For a long time after meeting Lao lan , Xiao Bai has not received any news from Lao LAN , Plus more classes , Xiaobai also slowly adapted to the day class , Playing games in the dormitory at night , Sometimes I go to the library to read books , This quiet life lasted almost two months . In the shadow of old blue ...

  2. 【Jersey】 be based on Jersey structure Restful Web application

    Environmental statement java: 1.6: tomcat: 6.0.48: Jersey:1.18: Jersey Introduce It's mainly used to build a system based on Restful Of Web Program : Build on Maven Of Javaweb Program explain : ...

  3. Hadoop Conclusion 5 --- How do modules drive execution

    stay MRv1 in , The driving mode between each module is function call . It's a synchronous process , The first mock exam module calls the first mock exam , Waiting for its execution . The efficiency is not high . stay MRv2 We have made improvements in ,yarn Concurrency model based on event driven . Before I go into details , Look at the picture below ...

  4. Ajax Step By Step5

    The fifth .[ Form serialization ] Ajax The most used place is form operation , The traditional form operation is through submit Submit the data to To the server . If you use Ajax Asynchronous processing , We need to get each form element one by one to get ...

  5. Git push Common use

        Git push In the use of git commit Command to commit changes from scratch to the local repository , Only the last step is to push the branch of the local version library to the corresponding branch on the remote server , If you don't know the composition of the repository , You can see another one of my ,g ...

  6. eq,neq,gt,lt And so on

    eq be equal to neq It's not equal to gt Greater than egt Greater than or equal to lt Less than elt Less than or equal to like LIKEbetween BETWEENnotnull IS NUT NULLnull IS NULL

  7. ARC The following may cause memory problems

    One .ARC relative MRC Come on , It reduces most of the memory management work of programmers , Use ARC Also need to be very clear when the principle of memory management , Otherwise, it may bring some problems that are difficult to debug . Here is ARC Here are some questions to pay attention to 1) Objects refer to each other , Form a reference ...

  8. JTAG Basic knowledge of

    Preface This knowledge translation collection comes from http://www.fpga4fun.com, The copyright belongs to the original website . 1. What is? JTAG:Joint Test Action Group: Joint test working group JTAG It's a kind of IEEE mark ...

  9. java.sql.SQLException: **** [SQLServer] Object name &quot;XXXX&quot; Invalid

    reason : Into the database , But no database was selected . Method : Check the data source configuration , It's easy to see . It's rare when you operate multiple databases , Switch data source !

  10. Python Built in functions (4)——ascii

    English document : ascii(object) As repr(), return a string containing a printable representation of an object, b ...