M_sea

洛谷2046 [NOI2010]海拔
LuoguBZOJ分析显然,左上一片$0$,右下一片$1$是最好的。要找出最小的分界线,就是求最小割的板子。然后数...
扫描右侧二维码阅读全文
12
2019/02

洛谷2046 [NOI2010]海拔

Luogu

BZOJ

分析

显然,左上一片$0$,右下一片$1$是最好的。

要找出最小的分界线,就是求最小割的板子。

然后数据范围很大,$\texttt{Dinic}$过不了???

发现原图是平面图,转为对偶图求最短路即可。

然后这个输入是真的毒瘤

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <queue>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=500+10;

struct Edge { int v,w,nxt; } e[2000010];
int head[250010];

inline void addEdge(int u,int v,int w) {
    static int cnt=0;
    e[++cnt]=(Edge){v,w,head[u]},head[u]=cnt;
}

struct HeapNode {
    int u,d;
    bool operator <(const HeapNode& rhs) const {
        return d>rhs.d;
    }
};
priority_queue<HeapNode> Q;
int dis[250010];

inline void dijkstra() {
    memset(dis,0x3f,sizeof(dis)); dis[0]=0;
    Q.push((HeapNode){0,0});
    while (!Q.empty()) {
        HeapNode x=Q.top(); Q.pop();
        int u=x.u,d=x.d;
        if (dis[u]!=d) continue;
        for (re int i=head[u];i;i=e[i].nxt) {
            int v=e[i].v,w=e[i].w;
            if (d+w<dis[v]) dis[v]=d+w,Q.push((HeapNode){v,dis[v]});
        }
    }
}

int g[N][N];

int main() {
    int n=read(),tot=0;
    for (re int i=1;i<=n;++i)
        for (re int j=1;j<=n;++j)
            g[i][j]=++tot;
    for (re int i=1;i<=n;++i) g[i][0]=g[n+1][i]=0,g[0][i]=g[i][n+1]=tot+1;
    for (re int i=1;i<=n+1;++i)
        for (re int j=1;j<=n;++j)
            addEdge(g[i][j],g[i-1][j],read());
    for (re int i=1;i<=n;++i)
        for (re int j=1;j<=n+1;++j)
            addEdge(g[i][j-1],g[i][j],read());
    for (re int i=1;i<=n+1;++i)
        for (re int j=1;j<=n;++j)
            addEdge(g[i-1][j],g[i][j],read());
    for (re int i=1;i<=n;++i)
        for (re int j=1;j<=n+1;++j)
            addEdge(g[i][j],g[i][j-1],read());
    dijkstra(); printf("%d\n",dis[tot+1]);
    return 0;
}
最后修改:2019 年 05 月 26 日 08 : 31 PM

发表评论