题解 P4134 【[BJOI2012]连连看】

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