$学了一些技巧$
1.二元组
$例题:bzoj2127 bzoj2132 bzoj3438 bzoj1976$
$对于这样一种题型:$
$i,j如果同属于/不同属于S或T获得收益w(i,j)$
$i属于S获得a[i],属于T获得b[i]$
$bzoj2132是这种问题的裸题$
$有一种独特的建图方法$
$insert(s, i, a[i])$
$insert(i, t, b[i])$
$insert(s, j, a[j])$
$insert(j, t, b[j])$
$insert(i, j, w(i, j))$
$insert(j, i, w(i, j))$
$然后跑最小割就行了，注意如果是属于不同集合那么把a[i],b[i]位置适当调换一下就行了,bzoj1976也可以这样解决$
$这种问题只适用于二元组，bzoj3438不能这样解决，只能用最大权闭合子图解$
$但是最大权闭合子图只能解决属于同一集合的问题，如bzoj2127;bzoj2132就无法$
$解决。$
$所以碰见同属一集合就用最大权闭合子图，否则就用二元组就行了。$
$2.最大权闭合子图$
$对于一些点之间的依赖关系，如果i依赖j,也就是选了j必须选i,那么insert(i, j, inf),$
$如果w[i] < 0 insert(i, sink, -w[i]), 否则 insert(source, i, w[i])$
$然后答案是sum_{w[i]>=0 } {w[i]} - dinic()$
$例题:bzoj3996$
$化简完变成sum_{i=1}^{n}sum_{j=1}^{n}{a_i*a_j*b_{ij}}-sum_{i=1}^{n}{b_i}$
$根据最大权闭合子图的定义，我们可以看出如果选择了某个c_i,那么对应的a_{i}=1。$
$所以如果某个b_{ij}选了，那么对应的c_i,c_j也得选$
$得出建图:insert(source, b -> ij, b_ij) insert(c -> i, sink, -c_i) 对于某个b_{ij},insert(b -> ij, c -> i, inf) insert(b -> ij, c -> j, inf)$
$最大权闭合子图解决$
$3.拆点$
$例题 bzoj1163 bzoj1570 bzoj1280 bzoj3144$
$限制点权:bzoj1163 比较明显的拆点$
$天数:bzoj1570 bzoj1280:把物品拆成每天，考虑连边$
$bzoj3144:限制相邻<=D,不算拆点吧，通过向相邻x-D的点连inf保证$
$4.线性规划$
$列出一些式子，把不等式通过加辅助变量变成等式，再添加两个0=0，差分，常数项>0从source连入，否则连向sink。变量>0连向<0$