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);
    }
}