首页 > 代码库 > BZOJ 2007 海拔（平面图最小割-最短路）

BZOJ 2007 海拔（平面图最小割-最短路）

2024-07-09 00:29:47   223人阅读

题目链接：http://61.187.179.132/JudgeOnline/problem.php?id=2007


题意：给出一个n*n的格子，那么顶点显然有(n+1)*(n+1)个。每两个相邻顶点之间有两条边，这两条边是有向的，边上有权值。。左上角为源点，右下角为汇点，求s到t的最小割。


思路：很明显这是一个平面图，将其转化为最短路。我们将s到t之间连一条边，左下角为新图的源点S，右上角区域为新图的终点T，并且为每个格子编号。由于边是有向的，我们就要分析下这条边应该是哪个点向哪个点的边。假设下图的红线是答案。比如<S,7>的那条边，必然是从上向下的，<6,5>那条边必然是从下向上的，<9,6>那条边必然是从左向右的，另外就是从右向左的边，必然是上面的格子到下面的格子。

vector<pair<int,int> > g[N];int n,dis[N];int get(int i,int j){    if(j==0||i==n+1) return 0;    if(i==0||j==n+1) return n*n+1;    return (i-1)*n+j;}priority_queue<pair<int,int> > Q;int SPFA(){    int i,s=0,t=n*n+1;    FOR0(i,t+1) dis[i]=INF;    dis[s]=0; Q.push(MP(0,s));    int u,v,c;    pair<int,int> p;    while(!Q.empty())    {        p=Q.top();        Q.pop();        u=p.second;        if(u==t) return -p.first;        FOR0(i,SZ(g[u]))        {            v=g[u][i].first;            c=g[u][i].second;            if(dis[v]>dis[u]+c)            {                dis[v]=dis[u]+c;                Q.push(MP(-dis[v],v));            }        }    }}int main(){    RD(n);    int i,j,x,s,t;    for(i=1;i<=n+1;i++) for(j=1;j<=n;j++)    {        RD(x);        t=get(i-1,j);        s=get(i,j);        g[s].pb(MP(t,x));    }    for(i=1;i<=n;i++) for(j=1;j<=n+1;j++)    {        RD(x);        s=get(i,j-1);        t=get(i,j);        g[s].pb(MP(t,x));    }    for(i=1;i<=n+1;i++) for(j=1;j<=n;j++)    {        RD(x);        s=get(i-1,j);        t=get(i,j);        g[s].pb(MP(t,x));    }    for(i=1;i<=n;i++) for(j=1;j<=n+1;j++)    {        RD(x);        t=get(i,j-1);        s=get(i,j);        g[s].pb(MP(t,x));    }    PR(SPFA());}

 

 


联系
我们