题目链接：

 

题目分析

首先，左上角的高度是 0 ，右下角的高度是 1。那么所有点的高度一定要在 0 与 1 之间。然而选取 [0, 1] 的任何一个实数，都可以用整数 0 或 1 来替换，获得同样的效果。

虽然输出的答案要求是四舍五入到整数，但其实答案就是一个整数！

那么高度就一定是 0 或 1 了，并且还有一点，所有选 0 的点都连通，所有选 1 的点都联通。因为如果一个选 0 的点被选 1 的点包围，那么它选 1 更优。

于是整个图中所有的点分成了与左上角相连的集合 A ，与右下角相连的集合 B 。从集合 A 向 B 的边权会计入答案。这就是最小割模型。

这是一个规则的平面图，平面图最小割等于对偶图最短路。

建立对偶图：

1）增加一条从 S 到 T 的边，成为 ST 边。这条边把原图中外围无限大的平面部分分割成了一个有限部分 S’ 和无限部分 T’。S’ 与 T’ 就是对偶图的起点和终点。

2）将平面的每个部分看做一个虚拟点，每条边对应一条连接虚拟点的边。但是 ST 边不对应对偶图中的边。

对偶图的一条最短路就对应了原图的一个最小割。

原图的每一条单向边对应对偶图的边的方向可以画个图帮助确定。可以看看从 S’ 到 T’ 的路径中哪些方向的边计入最小割答案，也应是最短路答案。

写 dijkstra ！卡 SPFA！

 

代码

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            using namespace std;const int MaxN = 500 + 5, INF = 999999999;int n, S, T;int Map[MaxN][MaxN][5], d[MaxN * MaxN];bool Visit[MaxN * MaxN];inline int Calc(int x, int y) {return (x - 1) * n + y;}struct Edge { int v, w; Edge *Next;} E[MaxN * MaxN * 4], *P = E, *Point[MaxN * MaxN];inline void AddEdge(int x, int y, int z) { ++P; P -> v = y; P -> w = z; P -> Next = Point[x]; Point[x] = P;}struct ES{ int x, y; ES() {} ES(int a, int b) { x = a; y = b; }};struct Cmp{ bool operator () (ES e1, ES e2) { return e1.y > e2.y; }};priority_queue
            
             , Cmp> Q;int main() { scanf("%d", &n); //Input data... for (int i = 1; i <= n + 1; ++i) for (int j = 1; j <= n; ++j) scanf("%d", &Map[i][j][0]); for (int i = 1; i <= n; ++i) for (int j = 1; j <= n + 1; ++j) scanf("%d", &Map[i][j][1]); for (int i = 1; i <= n + 1; ++i) for (int j = 2; j <= n + 1; ++j) scanf("%d", &Map[i][j][2]); for (int i = 2; i <= n + 1; ++i) for (int j = 1; j <= n + 1; ++j) scanf("%d", &Map[i][j][3]); //Input done... S = n * n + 1; T = n * n + 2; for (int i = 1; i <= n + 1; ++i) { for (int j = 1; j <= n + 1; ++j) { if (j <= n) { if (i == 1) AddEdge(Calc(i, j), T, Map[i][j][0]); else if (i == n + 1) AddEdge(S, Calc(i - 1, j), Map[i][j][0]); else AddEdge(Calc(i, j), Calc(i - 1, j), Map[i][j][0]); } if (j > 1) { if (i == 1) AddEdge(T, Calc(i, j - 1), Map[i][j][2]); else if (i == n + 1) AddEdge(Calc(i - 1, j - 1), S, Map[i][j][2]); else AddEdge(Calc(i - 1, j - 1), Calc(i, j - 1), Map[i][j][2]); } if (i <= n) { if (j == 1) AddEdge(S, Calc(i, j), Map[i][j][1]); else if (j == n + 1) AddEdge(Calc(i, j - 1), T, Map[i][j][1]); else AddEdge(Calc(i, j - 1), Calc(i, j), Map[i][j][1]); } if (i > 1) { if (j == 1) AddEdge(Calc(i - 1, j), S, Map[i][j][3]); else if (j == n + 1) AddEdge(T, Calc(i - 1, j - 1), Map[i][j][3]); else AddEdge(Calc(i - 1, j), Calc(i - 1, j - 1), Map[i][j][3]); } } } //Build_Edge done... memset(Visit, 0, sizeof(Visit)); for (int i = 1; i <= T; ++i) d[i] = INF; d[S] = 0; while (!Q.empty()) Q.pop(); ES Now; for (int i = 1; i <= T; ++i) Q.push(ES(i, d[i])); while (!Q.empty()) { Now = Q.top(); Q.pop(); if (Visit[Now.x]) continue; if (Now.x == T) break; Visit[Now.x] = true; for (Edge *j = Point[Now.x]; j; j = j -> Next) { if (d[Now.x] + j -> w < d[j -> v]) { d[j -> v] = d[Now.x] + j -> w; Q.push(ES(j -> v, d[j -> v])); } } } printf("%d\n", d[T]); return 0;}