HDU - 3035 War（对偶图求最小割+最短路） - 开发语言

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=3035

题意

给个图，求把s和t分开的最小割。

分析

实际顶点和边非常多，不能用最大流来求解。这道题要用平面图求最小割的方法：

把面变成顶点，对每两个面相邻的边作一条新边。然后求最短路就是最小割了。

另外，外平面分成两个点，分别是源点和汇点，源点连左下的边，汇点连右上的边，这样跑出来才是正确的。

建图参考自：https://blog.csdn.net/accelerator_/article/details/40957675

#include <cstdio>

#include <cstring>

#include <vector>

#include <queue>

using namespace std;

const int MAXNODE = ;

const int MAXEDGE =  * MAXNODE;

typedef int Type;

const Type INF = 0x3f3f3f3f;

struct Edge {

    int u, v;

    Type dist;

    Edge() {}

    Edge(int u, int v, Type dist) {

        this->u = u;

        this->v = v;

        this->dist = dist;

    }

};

struct HeapNode {

    Type d;

    int u;

    HeapNode() {}

    HeapNode(Type d, int u) {

        this->d = d;

        this->u = u;

    }

    bool operator < (const HeapNode& c) const {

        return d > c.d;

    }

};

struct Dijkstra {

    int n, m;

    Edge edges[MAXEDGE];

    int first[MAXNODE];

    int next[MAXEDGE];

    bool done[MAXNODE];

    Type d[MAXNODE];

    void init(int n) {

        this->n = n;

        memset(first, -, sizeof(first));

        m = ;

    }

    void add_Edge(int u, int v, Type dist) {

        edges[m] = Edge(u, v, dist);

        next[m] = first[u];

        first[u] = m++;

    }

    Type dijkstra(int s, int t) {

        priority_queue<HeapNode> Q;

        for (int i = ; i < n; i++) d[i] = INF;

        d[s] = ;

        memset(done, false, sizeof(done));

        Q.push(HeapNode(, s));

        while (!Q.empty()) {

            HeapNode x = Q.top(); Q.pop();

            int u = x.u;

            if (done[u]) continue;

            done[u] = true;

            for (int i = first[u]; i != -; i = next[i]) {

                Edge& e = edges[i];

                if (d[e.v] > d[u] + e.dist) {

                    d[e.v] = d[u] + e.dist;

                    Q.push(HeapNode(d[e.v], e.v));

                }

            }

        }

        return d[t];

    }

} gao;

typedef long long ll;

int n, m;

int main() {

    while (~scanf("%d%d", &n, &m)) {

        int u, v, w;

        gao.init(n * m *  + );

        int s = n * m * , t = n * m *  + ;

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

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

                scanf("%d", &w);

                u = (i - ) * m + j + n * m;

                v = i * m + j;

                if (i == ) u = t;

                if (i == n) v = s;

                gao.add_Edge(u, v, w);

                gao.add_Edge(v, u, w);

            }

        }

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

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

                scanf("%d", &w);

                u = n * m *  + i * m + j - ;

                v = n * m *  + i * m + j;

                if (j == ) u = s;

                if (j == m) v = t;

                gao.add_Edge(u, v, w);

                gao.add_Edge(v, u, w);

            }

        }

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

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

                scanf("%d", &w);

                u = i * m + j;

                v = n * m *  + i * m + j;

                gao.add_Edge(u, v, w);

                gao.add_Edge(v, u, w);

                scanf("%d", &w);

                v += n * m;

                gao.add_Edge(u, v, w);

                gao.add_Edge(v, u, w);

            }

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

                scanf("%d", &w);

                u = n * m + i * m + j;

                v = n * m *  + i * m + j;

                gao.add_Edge(u, v, w);

                gao.add_Edge(v, u, w);

                scanf("%d", &w);

                v += n * m;

                gao.add_Edge(u, v, w);

                gao.add_Edge(v, u, w);

            }

        }

        printf("%d\n", gao.dijkstra(s, t));

    }

    return ;

}