bzoj 2007 [Noi2010]海拔——最小割转最短路

时间：2023-03-09 19:09:52
bzoj 2007 [Noi2010]海拔——最小割转最短路

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

一个点的高度一定不是0就是1。答案一定形如一个左上角的连通块全是0的点、一个右下角的连通块全是1的点。

注意从东到西还有从南到北的边也有用！因为不一定是一个阶梯形的，还可以拐来拐去，只是一定是两个连通块罢了。

所以最小割一下那个分界线就行了。但会TLE。

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int N=*+,M=*+,INF=2e6+;

int n,t,bh[][],hd[N],xnt=,cur[N],to[M],nxt[M],cap[M];

int dfn[N],q[N],he,tl;

int Mn(int a,int b){return a<b?a:b;}

int rdn()

{

    int ret=;bool fx=;char ch=getchar();

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

    while(ch>=''&&ch<='')ret=ret*+ch-'',ch=getchar();

    return fx?ret:-ret;

}

void add(int x,int y,int z)

{

    to[++xnt]=y;nxt[xnt]=hd[x];hd[x]=xnt;cap[xnt]=z;

    to[++xnt]=x;nxt[xnt]=hd[y];hd[y]=xnt;cap[xnt]=;

}

bool bfs()

{

    memset(dfn,,sizeof dfn);dfn[]=;

    q[he=tl=]=;

    while(he<=tl)

    {

        int k=q[he++];

        for(int i=hd[k],v;i;i=nxt[i])

            if(cap[i]&&!dfn[v=to[i]])

                dfn[v]=dfn[k]+,q[++tl]=v;

    }

    return dfn[t];

}

int dinic(int cr,int flow)

{

    if(cr==t)return flow;

    int use=;

    for(int& i=cur[cr],v;i;i=nxt[i])

        if(cap[i]&&dfn[v=to[i]]==dfn[cr]+)

        {

            int tmp=dinic(v,Mn(flow-use,cap[i]));

            if(!tmp)dfn[v]=;

            use+=tmp;cap[i]-=tmp;cap[i^]+=tmp;

            if(use==flow)return use;

        }

    return use;

}

int main()

{

    n=rdn();

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

        for(int j=;j<=n;j++)bh[i][j]=t++;

    t--; int d;

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

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

            d=rdn(),add(bh[i][j-],bh[i][j],d);

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

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

            d=rdn(),add(bh[i-][j],bh[i][j],d);

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

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

            d=rdn(),add(bh[i][j],bh[i][j-],d);

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

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

            d=rdn(),add(bh[i][j],bh[i-][j],d);

    int ans=;

    while(bfs())memcpy(cur,hd,sizeof hd),ans+=dinic(,INF);

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

    return ;

}

可以转成最短路。注意边的方向。

学习了学长的不显式建图的方法。大概 dis[ ][ ] 记录的就是从起点走到格子的距离，再记4个 dis[ ][ ] 表示它的周围4条边的容量，之类的。

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<queue>

using namespace std;

const int N=,INF=2e6+;

int n,dis[][N][N],ans=INF;bool vis[N][N];

struct Node{

    int x,y,dis;

    Node(int a=,int b=,int d=):x(a),y(b),dis(d) {}

    bool operator< (const Node &b)const

    {return dis>b.dis;}

};

priority_queue<Node> q;

int Mn(int a,int b){return a<b?a:b;}

int rdn()

{

    int ret=;bool fx=;char ch=getchar();

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

    while(ch>=''&&ch<='')ret=ret*+ch-'',ch=getchar();

    return fx?ret:-ret;

}

void add(int x,int y,int d)

{

    if(d<dis[][x][y])

        dis[][x][y]=d,q.push(Node(x,y,d));

}

void dj()

{

    for(int i=;i<=n;i++)add(,i,dis[][][i]);

    for(int i=;i<=n;i++)add(i,n,dis[][i][n+]);

    while(q.size())

    {

        int x=q.top().x,y=q.top().y,d=q.top().dis; q.pop();

        if(vis[x][y])continue; vis[x][y]=;

        if(x<n)add(x+,y,d+dis[][x+][y]);//x+1(up)

        if(y>)add(x,y-,d+dis[][x][y]);

        if(x>)add(x-,y,d+dis[][x-][y]);//x-1(dn)

        if(y<n)add(x,y+,d+dis[][x][y]);

    }

    for(int i=;i<=n;i++)ans=Mn(ans,dis[][i][]+dis[][i][]);

    for(int i=;i<=n;i++)ans=Mn(ans,dis[][n][i]+dis[][n+][i]);//n+1

}

int main()

{

    n=rdn();int d=n+;

    for(int i=;i<=d;i++)

        for(int j=;j<=n;j++)dis[][i][j]=rdn();//up

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

        for(int j=;j<=d;j++)dis[][i][j]=rdn();//left

    for(int i=;i<=n;i++)//0~n & 1~n !!!

        for(int j=;j<=n;j++)dis[][i][j]=rdn();//dn

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

        for(int j=;j<=n;j++)dis[][i][j]=rdn();//right

    memset(dis[],0x3f,sizeof dis[]);

    dj();

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

    return ;

}

相关文章