emmmmm.......这数据范围.....应该是费用流

然而楼下dalao所说的二分图我不会证啊qwq

没办法,只能硬想了.

咳咳,言归正传

算法

这题的特点有两个:

• 每个数最多被消一次..........(记为条件1)

• 要消就是一对点一起消..........(记为条件2)

所以,不难建出图:

• 把一个数拆成两个点,分别记为$In_x$和$Out_x$,表示"输入"和"输出".

• 从$S$向每个数的输出端($Out_x$)连一条(1,0)的边$\qquad\color{blue}{\text{注:(1,0)代表流量为1,单位流量费用为0}}$

• 从每个数的输入端($In_x$)向$T$连一条(1,0)的边

• 对于符合条件的两个数$x,y$,从$Out_x$向$In_y$连$(1,x+y)$,从$Out_y$向$In_x$连$(1,x+y)$ 前三条好理解,最后一条是在干啥?

道理很简单:为了保证"条件2".(自己想想如果只连了$In_x$和$Out_y$会怎样).输出答案时,直接将费用与流量分别除以2即可

一个要注意的地方 & 关键点

有人说自己求最大费用最大流$WA$了(只得30分)

这是为什么呢?

答案就是你们初始化时把$Dis$全设为$-1$而不是$-\inf$

不要忘了反向弧的费用为负

这样就会导致某些点到$S$的距离小于你设的初始权值

代码(只有建图部分我相信你们都有模板)

bool Ok( int x , int y ){
    if( x < y ) swap(x,y);
    int z = x*x - y*y;
    int d = sqrt(z);
    if( d*d != z ) return 0;
    if( __gcd(d,y) != 1 ) return 0;
    return 1;
}

void Build(){
    Forx(i,a,b)
        Forx(j,i+1,b)
            if(Ok(i,j)){
                int point = i+j;
                Link(i,j+MAXN,1,point);
                Link(j,i+MAXN,1,point);
            }
    Forx(i,a,b){
        Link(S,i,1,0);
        Link(i+MAXN,T,1,0);
    }
}