bzoj2661 [BeiJing wc2012]连连看

()
Description

凡是考智商的题里面总会有这么一种消除游戏。不过现在面对的这关连连看可不是QQ游戏里那种考眼力的游戏。我们的规则是，给出一个闭区间[a,b]中的全部整数，如果其中某两个数x,y（设x>y）的平方差x2-y2是一个完全平方数z2，并且y与z互质，那么就可以将x和y连起来并且将它们一起消除，同时得到x+y点分数。那么过关的要求就是，消除的数对尽可能多的前提下，得到足够的分数。快动手动笔算一算吧。
Input

只有一行，两个整数，分别表示a,b。
Output

两个数，可以消去的对数，及在此基础上能得到的最大分数。
Sample Input
1 15
Sample Output
2 34
HINT

对于30%的数据，1<=a,b<=100

对于100%的数据，1<=a,b<=1000

思想很妙 通过这题其实还可以知道一个性质 x^2-y^2=z^2且gcd(y,z)=1时 gcd(x,y)一定是1

那么假设我x,y 存在最大公约数p 那么x=px1,y=py1原式=p^2*x1^2-p^2*y1^2=z^2

因为x1^2-y1^2一定是整数 所以z一定是P的倍数与题设矛盾 wcc gcd再次写错 应该是return gcd(y,x%y)

那这题的解法 应该是什么样的？我首先把每个数拆成两个点 然后 如果两个数符合条件 那么我就把i->j+n j->i+n连上容量为1 边权为i+j的边 跑最大费用最大流即可 最后输出的时候都÷2即可 为什么呢 因为这是两条一样的边哦选了一个一定会选另一个

#include<cmath>
#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N  2200
#define inf 0x3f3f3f3f
using namespace std;
inline char gc(){
    static char now[1<<16],*S,*T;
    if (T==S){T=(S=now)+fread(now,1,1<<16,stdin);if (T==S ) return EOF;}
    return *S++;
}
inline int read(){
    int x=0;char ch=gc();
    while(ch<'0'||ch>'9') ch=gc();
    while(ch<='9'&&ch>='0'){x=x*10+ch-'0';ch=gc();}
    return x;
}
struct node{
    int y,z,next,c;
}data[20000];
inline int gcd(int x,int y){if (y==0) return x;return gcd(y,x%y);}
int num=1,a,b,h[N],f[N],flag[N],pre[N],path[N],T;
inline void insert1(int x,int y,int z,int c){
    data[++num].y=y;data[num].next=h[x];data[num].z=z;data[num].c=c;h[x]=num;
    data[++num].y=x;data[num].next=h[y];data[num].z=0;data[num].c=-c;h[y]=num;
}
inline bool spfa(){
    memset(f,128,sizeof(f));memset(flag,0,sizeof(flag));queue<int>q;memset(pre,-1,sizeof(pre));q.push(0);f[0]=0;flag[0]=1;
    while(!q.empty()){
        int x=q.front();q.pop();flag[x]=0;
        for (int i=h[x];i;i=data[i].next){
            int y=data[i].y,z=data[i].z,c=data[i].c;
            if (f[x]+c>f[y]&&z){
                f[y]=f[x]+c;pre[y]=x;path[y]=i;
                if (!flag[y]) q.push(y),flag[y]=1;
            }
        }
    }if(pre[T]==-1) return 0;else return 1;
}
int main(){
    freopen("bzoj2661.in","r",stdin);
    a=read();b=read();int n=1000;T=n*2+1;
    for (int i=a;i<=b;++i){
        for (int j=i+1;j<=b;++j){
            if (gcd(i,j)!=1) continue;int sum=j*j-i*i;int nn=sqrt(sum);if (nn*nn!=sum) continue;
            insert1(i,j+n,1,i+j);insert1(j,i+n,1,i+j);
        }
    }for (int i=a;i<=b;++i) insert1(0,i,1,0),insert1(i+n,T,1,0);int ans=0,ans1=0;
    while(spfa()){
        int minn=inf,now=T;
        while(now) minn=min(minn,data[path[now]].z),now=pre[now];ans+=minn;now=T;
        while(now) {ans1+=data[path[now]].c*minn;data[path[now]].z-=minn;data[path[now]^1].z+=minn;now=pre[now];}
    }printf("%d %d\n",ans>>1,ans1>>1);
    return 0;
}