[衡阳八中OJ 1001]对偶图、用最短路求平面图的最小割

【题目】http://61.187.179.132:8080/JudgeOnline/showproblem?problem_id=1001

【题目大意】给出一个矩阵型的图,求左上角到右下角的最小割。边都是无向的。

【算法分析】把面看成图,然后可以通过跨越边的方式到达另外一端,跨过边就相当于去这条边为割集的一部分,最后求右上角这个面,到最下角这个面的最短路即可

【其它】NWA,注意N=1 OR M=1的情况请特判。

【CODE】

#include

留下评论

您的电子邮箱地址不会被公开。