BZOJ 2007 海拔(平面图最小割转对偶图最短路)

时间：2023-03-09 19:09:53
BZOJ 2007 海拔(平面图最小割转对偶图最短路)

首先注意到，把一个点的海拔定为>1的数是毫无意义的。实际上，可以转化为把这些点的海拔要么定为0，要么定为1.

其次，如果一个点周围的点的海拔没有和它相同的，那么这个点的海拔也是可以优化的，即把这个点变为周围海拔一样的显然能使结果变优。

于是问题就变成了，这个图的海拔为0的联通块和起点连在一起，海拔为1的联通块和终点连在一起。

此即为经典的最小割。

由于此图为平面图，我们可以使用平面图最小割转对偶图最短路优化算法。

因为这是有向图，因此构建对偶图的时候注意边的方向即可。

# include <cstdio>

# include <cstring>

# include <cstdlib>

# include <iostream>

# include <vector>

# include <queue>

# include <stack>

# include <map>

# include <set>

# include <cmath>

# include <algorithm>

using namespace std;

# define lowbit(x) ((x)&(-x))

# define pi acos(-1.0)

# define eps 1e-

# define MOD

# define INF 1e16

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

# define FOR(i,a,n) for(int i=a; i<=n; ++i)

# define FO(i,a,n) for(int i=a; i<n; ++i)

# define bug puts("H");

# define lch p<<,l,mid

# define rch p<<|,mid+,r

# define mp make_pair

# define pb push_back

typedef pair<int,int> PII;

typedef vector<int> VI;

# pragma comment(linker, "/STACK:1024000000,1024000000")

typedef long long LL;

int Scan() {

    int x=,f=;char ch=getchar();

    while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

    while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

    return x*f;

}

void Out(int a) {

    if(a<) {putchar('-'); a=-a;}

    if(a>=) Out(a/);

    putchar(a%+'');

}

const int N=;

//Code begin...

struct Edge{int p, next; LL w;}edge[N*];

struct qnode{

    int v; LL c;

    qnode(int _v=, LL _c=):v(_v),c(_c){}

    bool operator<(const qnode&r)const{return c>r.c;}

};

bool vis[N];

int head[N], cnt=;

LL G1[][], G2[][], G3[][], G4[][], dist[N];

priority_queue<qnode>que;

void add_edge(int u, int v, LL w){edge[cnt].p=v; edge[cnt].w=w; edge[cnt].next=head[u]; head[u]=cnt++;}

void Dijkstra(int n, int start){

    mem(vis,false); FOR(i,,n) dist[i]=INF;

    dist[start]=; que.push(qnode(start,));

    qnode tmp;

    while (!que.empty()) {

        tmp=que.top(); que.pop();

        int u=tmp.v;

        if (vis[u]) continue;

        vis[u]=true;

        for (int i=head[u]; i; i=edge[i].next) {

            int v=edge[i].p; LL cost=edge[i].w;

            if (!vis[v]&&dist[v]>dist[u]+cost) dist[v]=dist[u]+cost, que.push(qnode(v,dist[v]));

        }

    }

}

int main ()

{

    int n, s, t, x;

    scanf("%d",&n); s=; t=n*n+;

    FOR(i,,n) FOR(j,,n) scanf("%lld",&G1[i][j]);

    FOR(i,,n) FOR(j,,n) scanf("%lld",&G2[i][j]);

    FOR(i,,n) FOR(j,,n) scanf("%lld",&G3[i][j]);

    FOR(i,,n) FOR(j,,n) scanf("%lld",&G4[i][j]);

    FOR(i,,n) FOR(j,,n) {

        if (i==) add_edge(s,i*n+j,G1[i][j]), add_edge(i*n+j,s,G3[i][j]);

        else if (i==n) add_edge((i-)*n+j,t,G1[i][j]), add_edge(t,(i-)*n+j,G3[i][j]);

        else add_edge((i-)*n+j,i*n+j,G1[i][j]), add_edge(i*n+j,(i-)*n+j,G3[i][j]);

    }

    FOR(i,,n) FOR(j,,n) {

        if (j==) add_edge((i-)*n+j+,t,G2[i][j]), add_edge(t,(i-)*n+j+,G4[i][j]);

        else if (j==n) add_edge(s,(i-)*n+j,G2[i][j]), add_edge((i-)*n+j,s,G4[i][j]);

        else add_edge((i-)*n+j+,(i-)*n+j,G2[i][j]), add_edge((i-)*n+j,(i-)*n+j+,G4[i][j]);

    }

    Dijkstra(t,s);

    printf("%lld\n",dist[t]);

    return ;

}

相关文章