2007: [Noi2010]海拔

https://www.lydsy.com/JudgeOnline/problem.php?id=2007

分析：

　　平面图最小割。

　　S在左下，T在右上，从S到T的一个路径使得路径右下方全是1，左上方全是0。

　　一个问题：每个点的高度只能是0/1，所以有些边是一定不能选的，就让它连向S，不影响。

代码：

 /*

 平面图最小割

 */

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 #include<iostream>

 #include<cctype>

 #include<queue>

 using namespace std;

 typedef long long LL;

 inline int read() {

     int x = , f = ; char ch = getchar(); for (; !isdigit(ch); ch=getchar()) if (ch=='-') f = -;

     for (; isdigit(ch); ch=getchar()) x = x *  + ch - ''; return x * f;

 }

 const int N = ;

 struct Edge{

     int to, w, nxt;

     Edge() {}

     Edge(int a,int b,int c) {to = a, w = b, nxt = c;}

 }e[];

 struct Node{

     int u;

     LL dis;

     Node() {}

     Node(int a,LL b) {u = a, dis = b;}

     bool operator < (const Node &A) const {

         return dis > A.dis;

     }

 };

 int head[N];

 LL dis[N];

 int Enum, n;

 bool vis[N];

 priority_queue<Node> q;

 void add_edge(int u,int v,int w) {

     e[++Enum] = Edge(v, w, head[u]); head[u] = Enum;

 //    cout << u << " " << v << " " << w << '\n';

 }

 int get(int i,int j) {

     return (i - ) * n + j;

 }

 int Dijkstra(int S,int T) {

     for (int i=; i<=T; ++i) dis[i] = 1e18, vis[i] = false;

     dis[S] = ;

     q.push(Node(S,));

     Node now, nxt;

     while (!q.empty()) {

         now = q.top(); q.pop();

         int u = now.u;

         if (vis[u]) continue;

         vis[u] = true;

         for (int i=head[u]; i; i=e[i].nxt) {

             int v = e[i].to;

             if (dis[v] > dis[u] + e[i].w) {

                 dis[v] = dis[u] + e[i].w;

                 q.push(Node(v,dis[v]));

             }

         }

     }

     return dis[T];

 }

 int main() {

     n = read();

     int S = , T = n * n + ;

     for (int i=; i<=n+; ++i) { // 左 -> 右， 下 -> 上

         for (int j=; j<=n; ++j) {

             int w = read();

             if (i == ) add_edge(get(i, j), T, w);

             else if (i == n + ) add_edge(S, get(i - , j), w);

             else add_edge(get(i, j), get(i - , j), w);

         }

     }

     for (int i=; i<=n; ++i) { // 上 -> 下 ， 左 -> 右

         for (int j=; j<=n+; ++j) {

             int w = read();

             if (j == ) add_edge(S, get(i, j), w);

             else if (j == n + ) add_edge(get(i, j - ), T, w);

             else add_edge(get(i, j - ), get(i, j), w);

         }

     }

     for (int i=; i<=n+; ++i) { // 右 -> 左 ， 上 -> 下

         for (int j=; j<=n; ++j) {

             int w = read();

             if (i == ) add_edge(T, get(i, j), w);

             else if (i == n + ) add_edge(get(i - , j), S, w);

             else add_edge(get(i - , j), get(i, j), w);

         }

     }

     for (int i=; i<=n; ++i) { // 下 -> 上 ， 右 - > 左

         for (int j=; j<=n+; ++j) {

             int w = read();

             if (j == ) add_edge(get(i, j), S, w);

             else if (j == n + ) add_edge(T, get(i, j - ), w);

             else add_edge(get(i, j), get(i, j - ), w);

         }

     }

     printf("%d",Dijkstra(S, T));

     return ;

 }