题目链接

 #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read()
{
int x=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}
return x*f;
} /********************************************************************/ #define inf 0xffffff
#define T 2001
const int maxn = 2e6+;
const int Maxn = 2e3+;
int a, b;
int ans1, ans2;
int head[Maxn], q[Maxn], dis[Maxn], from[Maxn];
bool vis[Maxn]; struct node
{
int to, from, Next;
int v, c;
}e[maxn];
int cnt = ; int gcd(int x, int y){
if(y == ) return x;
else return gcd(y, x%y);
} void add_edge(int u, int v, int w, int c){
e[++cnt].to = v; e[cnt].from = u; e[cnt].Next = head[u]; head[u] = cnt;
e[cnt].v = w; e[cnt].c = c;
} void insert(int u, int v, int w, int c){
add_edge(u, v, w, c);
add_edge(v, u, , -c);
} //是否满足条件
bool check(int x, int y){
if(x < y) swap(x, y);
int t = int(sqrt(x*x-y*y));
return (gcd(y, t) == && x*x-y*y == t*t);
} bool spfa(){
for(int i = ;i <= T;i++){
dis[i] = -inf;
}
int t = , w = ;
dis[] = ; q[] = ; vis[] = ;
while(t != w){
int now = q[t]; t++;
if(t == T) t = ;
for(int i = head[now];i;i = e[i].Next){
if(e[i].v && e[i].c+dis[now] > dis[e[i].to]){
dis[e[i].to] = e[i].c + dis[now];
from[e[i].to] = i;
if(!vis[e[i].to]){
vis[e[i].to] = ;
q[w++] = e[i].to;
if(w == T) w = ;
}
}
}
vis[now] = ;
}
if(dis[T] == -inf) return false;
return true;
} void dfs(){
int x = inf;
for(int i = from[T];i;i = from[e[i].from]){
x = min(e[i].v, x);
}
for(int i = from[T];i;i = from[e[i].from]){
ans2 += x*e[i].c;
e[i].v -= x;
e[i^].v += x;
}
} int main(){
a = read(); b = read();
for(int i = a;i <= b;i++){
for(int j = a;j <= b;j++){
if(check(i, j) && i != j){
insert(i, j+, , i+j);
}
}
}
for(int i = a;i <= b;i++){
insert(, i, , );
insert(i+, T, , );
}
while(spfa()) dfs();
for(int i = ;i <= cnt;i += ){
if()
}
return ;
}
05-23 01:16