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