如果只会用最小割做这道题那就太菜辣

引入

来自某学长

平面图：在平面上边不相交的图（边可以绕着画）

那么平面图的边与边就围成了许多个区域（这与你画图的方式有关）

定义对偶图：把相邻的两个区域连上边，形成的图

两个可能正确的东西：

对偶图\(\in\)平面图
平面图的对偶图的对偶图是它自己

知道这些再来写这道题就够了

Sol

题目给了一个确定的平面图

考虑在起点处和终点处以它为起点画一条斜射线，把平面分成左下和右上两个部分，分别定义为\(S\)和\(T\)

然后建立对偶图边权就是跨过的平面图的边权（\(S\)和\(T\)不直接相连），求一遍\(S\)到\(T\)的最短路即可

理解：一条\(S\)到\(T\)的路径把这个平面图的起点和终点隔开，那么最短路就是最小割

建图比较恶心

# include <bits/stdc++.h>

# define RG register

# define IL inline

# define Fill(a, b) memset(a, b, sizeof(a))

using namespace std;

typedef long long ll;

const int _(6e6 + 5);

IL ll Input(){

    RG ll x = 0, z = 1; RG char c = getchar();

    for(; c < '0' || c > '9'; c = getchar()) z = c == '-' ? -1 : 1;

    for(; c >= '0' && c <= '9'; c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48);

    return x * z;

}

int n, m, fst[_], nxt[_], w[_], to[_], cnt, dis[_], S, T, vis[_], id[1005][1005], num;

queue <int> Q;

IL void Add(RG int u, RG int v, RG int ww){

    nxt[cnt] = fst[u]; to[cnt] = v; w[cnt] = ww; fst[u] = cnt++;

}

IL int SPFA(){

    Fill(dis, 127); dis[S] = 0;

    vis[S] = 1; Q.push(S);

    while(!Q.empty()){

        RG int u = Q.front(); Q.pop();

        for(RG int e = fst[u]; e != -1; e = nxt[e])

            if(dis[u] + w[e] < dis[to[e]]){

                dis[to[e]] = dis[u] + w[e];

                if(!vis[to[e]]) vis[to[e]] = 1, Q.push(to[e]);

            }

        vis[u] = 0;

    }

    return dis[T];

}

int main(RG int argc, RG char* argv[]){

    Fill(fst, -1); n = Input(); m = Input();

    for(RG int i = 1, r = (n - 1) * 2; i <= r; ++i)

        for(RG int j = 1; j < m; ++j)

            id[i][j] = ++num;

    T = num + 1;

    for(RG int i = 1, I = 1; i <= n; ++i, I += 2)

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

            RG int v = Input(), id1 = S, id2 = T;

            if(i != 1) id2 = id[I - 1][j];

            if(i != n) id1 = id[I][j];

            Add(id1, id2, v); Add(id2, id1, v);

        }

    for(RG int i = 1, I = 1; i < n; ++i, I += 2)

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

            RG int v = Input(), id1 = S, id2 = T;

            if(j != 1) id1 = id[I][j - 1];

            if(j != m) id2 = id[I + 1][j];

            Add(id1, id2, v); Add(id2, id1, v);

        }

    for(RG int i = 1, I = 1; i < n; ++i, I += 2)

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

            RG int v = Input(), id1 = id[I][j], id2 = id[I + 1][j];

            Add(id1, id2, v); Add(id2, id1, v);

        }

    printf("%d\n", SPFA());

    return 0;

}

巴特西

平面图转对偶图(Bzoj1001：狼抓兔子)

引入

Sol

最新文章

热门文章