一些 tricks
-
最小割的可行边和必须边判定
-
可行边：
-
满流。
-
在残余网络中找不到 \(u\rightarrow v\) 的路径。
-
-
必须边：
-
满流
-
残余网络中源点能到入点, 出点能到汇点。
-
证明
-
-
向量点积的几何意义和代数意义：
-
代数意义：\(\vec a=(x_1,y_1),\vec b=(x_2,y_2)\)。\(\vec a\cdot\vec b=x_1x_2+y_1y_2\)。
-
几何意义：设 \(\vec a,\vec b\) 夹角为 \(\theta\)，有 \(\vec a\cdot\vec b=|\vec a|\times|\vec b|\times\cos\theta\)。
证明
-