网络流——平面图最小割
问题
对一个平面无向图，求最小割。
通俗理解
因为这是平面图，没有边相交，所以它的最小割，一定可以用铅笔画一条线，把图的S,T两点分在两边，使得铅笔线穿过的边权值最小。
于是可以建立把原图分为上下两部分，并建立对偶图，使得对偶图的边权为原图的边权：
于是从S到T的最短路，就是原图的最小割（权值最小的铅笔线）
关于如何判断S，T点：连一条原图S->T的边在最外面，有框出来一个新的平面为S，外面的为T
一道题
BZOJ1001
对一个平面无向图，求最小割。
因为这是平面图，没有边相交，所以它的最小割，一定可以用铅笔画一条线，把图的S,T两点分在两边，使得铅笔线穿过的边权值最小。
于是可以建立把原图分为上下两部分，并建立对偶图，使得对偶图的边权为原图的边权：
于是从S到T的最短路，就是原图的最小割（权值最小的铅笔线）
关于如何判断S，T点：连一条原图S->T的边在最外面，有框出来一个新的平面为S，外面的为T
BZOJ1001