题解 P4134 【[BJOI2012]连连看】
interestingLSY
2018-07-28 13:17:54
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$的距离小于你设的初始权值
# 代码(只有建图部分~~我相信你们都有模板~~)
```cpp
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);
}
}
```