线性规划、对偶、费用流

[max mathbf{C}^Tmathbf{x}\ mathbf{Ax}leqmathbf{B}\ mathbf{x}geq 0\ Updownarrow\ min mathbf{B}^Tmathbf{y}\ mathbf{A}^Tmathbf{y}geqmathbf{C}\ mathbf{y}geq 0 ]

[(u,v,c_{u,v},w_{u,v})\ (S,u,b_u,0),b_u>0\ (u,T,-b_u,0),b_u<0\ Updownarrow\ min sum w_{u,v}f_{u,v}\ -f_{u,v}geq -c_{u,v}\ sum f_{v,u}-sum f_{u,v}geq -b_u\ f_{u,v}geq 0\ Updownarrow\ max sum -c_{u,v}z_{u,v}-sum -b_up_u\ p_v-p_u-z_{u,v}leq w_{u,v}\ z_{u,v},p_ugeq 0\ Updownarrow\ -minsum b_up_u+sum c_{u,v}max(0,p_v-p_u-w_{u,v}) ]