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

每个点拆成两个，可以消掉的连边，然后在二分图中做一次费用流即可。

代码（原始对偶算法）：

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
#include <cmath>
 
using namespace std;
 
#define MAXN 1010
#define inf 0x7fffffff
#define MAXV 2010
 
struct edge {
    int t,f,c;
    edge *pair,*next;
    edge () {
        pair=next=NULL;
    }
} *head[MAXV];
 
void Add(int s,int t,int f,int c) {
    edge *p=new(edge);
    p->t=t,p->f=f,p->c=c,p->next=head[s];
    head[s]=p;
}
 
void AddEdge(int s,int t,int f,int c) {
    Add(s,t,f,c),Add(t,s,0,-c);
    head[s]->pair=head[t],head[t]->pair=head[s];
}
 
int dist[MAXV],V,S,T,maxflow=0,cost=0;
bool f[MAXV];
queue<int>Q;
 
bool spfa() {
    for (int i=0;i++<V;) dist[i]=-inf,f[i]=true;
    Q.push(S),dist[S]=0;
    while (!Q.empty()) {
        int v=Q.front();
        Q.pop();
        if (!f[v]) continue;
        f[v]=false;
        for (edge *p=head[v];p;p=p->next) if (p->f&&dist[p->t]<dist[v]+p->c) {
            dist[p->t]=dist[v]+p->c,Q.push(p->t),f[p->t]=true;
        }
    }
    return dist[T]>-inf;
}
 
int aug(int v,int flow) {
    if (v==T) {
        cost+=dist[T]*flow,maxflow+=flow;
        return flow;
    }
    int rec=0;
    f[v]=false;
    for (edge *p=head[v];p;p=p->next) if (p->f&&f[p->t]&&dist[p->t]==dist[v]+p->c) {
        int ret=aug(p->t,min(flow-rec,p->f));
        p->f-=ret,p->pair->f+=ret;
        if ((rec+=ret)==flow) return flow;
    }
    return rec;
}
 
void costflow() {
    while (spfa()) {
        do {
            memset(f,true,sizeof(f));
        } while (aug(S,inf));
    }
}
 
int a,b,v[MAXN][2];
 
int gcd(int x,int y) {
    if (!y) return x;
    return gcd(y,x%y);
}
 
bool check(int x,int y) {
    if (x<y)swap(x,y);
    return gcd(x,y)==1&&x*x-y*y==int(sqrt(x*x-y*y))*int(sqrt(x*x-y*y));
}
 
int main() {
    scanf("%d%d",&a,&b);
    S=++V,T=++V;
    memset(head,0,sizeof(head));
    for (int i=a;i<=b;i++)AddEdge(S,v[i][0]=++V,1,0)    ,AddEdge(v[i][1]=++V,T,1,0);
    for (int i=a;i<=b;i++) for (int j=a;j<=b;j++) if (i!=j&&check(i,j))AddEdge(v[i][0],v[j][1],1,i+j);
    costflow();
    printf("%d %d\n",maxflow>>1,cost>>1);
    return 0;
}