飞鸟和蝉 题解

冷月葬T魂 · 2021-08-12 11:36:29 · 题解

考虑建模。从每个格子向周围海拔较低的格子连一条有向边，则网格就变成了一个有向无环图。类似于有向路径剖分，再建一个二分图，将每个点 u 拆成 u 和 u' 两个点，对于每条有向边 (u,v)，在二分图中连接 u 和 v'，于是跳跃的一条路径 (a_1,a_2,\dots,a_k) 就成为了一系列匹配边 (a_1,a_2'),(a_2,a_3'),\dots,(a_{n-1},a_n')。
再回到我们的目标，“飞行次数最少”就是非匹配点数最少，即匹配边数最多，这不就是最大匹配吗！再考虑费用（即体力值）。设一共有 m 条路径，第 i 条路径的起点、终点的海拔分别为 s_i,t_i。则消耗的总体力值为（记 s_{m+1}=s_1）：

这是什么？这就是“每条路径的起点与终点海拔之差”的和！
这又是什么？这就是每条路径上走过的“每条边的海拔之差”之和！——即 a_1-a_n=(a_1-a_2)+(a_2-a_3)+\dots+(a_{n-1}-a_n)
现在思路很清楚了，二分图中每条边设容量为1，费用为“这条边起点与终点海拔之差”，再设一个源一个汇，求最小费用最大流即可。
附上代码：

#include <bits/stdc++.h>
#define For(i,a,b) for(int i=a;i<=b;i++)
#define Rev(i,a,b) for(int i=a;i>=b;i--)
#define clr(a,val) memset(a,val,sizeof(a))
#define int long long
using namespace std;

namespace cpdd{
    const int N=2e5+5;

    int n,m,S,T,head[N],nxt[N],to[N],cp[N],cv[N],tot;
    int ans,maxflow;

    void add(int x,int y,int z,int w)
    {
        nxt[++tot]=head[x];
        head[x]=tot;
        to[tot]=y;
        cp[tot]=z;
        cv[tot]=w;

        nxt[++tot]=head[y];
        head[y]=tot;
        to[tot]=x;
        cp[tot]=0;
        cv[tot]=-w;
    }

    int q[N],h,t,dis[N],inq[N],incf[N],prev[N];

    bool spfa()
    {
        clr(dis,0x3f);

        h=t=0;
        q[t++]=S;
        dis[S]=0;
        inq[S]=1;
        incf[S]=1e9;

        while(h<t){
            int u=q[h++];
            inq[u]=0;

            for(int e=head[u];e;e=nxt[e]){
                if(!cp[e]) continue;

                int v=to[e];
                if(dis[v]>dis[u]+cv[e]){
                    dis[v]=dis[u]+cv[e];
                    incf[v]=min(incf[u],cp[e]);
                    prev[v]=e;
                    if(!inq[v]){
                        inq[v]=1;
                        q[t++]=v;
                    }
                }
            }
        }

        return dis[T]<dis[0];
    }

    void update()
    {
        int p=T,f=incf[T];

        while(p!=S){
            int e=prev[p];
            cp[e]-=f;
            cp[e^1]+=f;
            p=to[e^1];
        }

        maxflow+=f;
        ans+=f*dis[T];
    }

    void solve(int& _maxflow,int& _ans)
    {
        while(spfa()) update();

        _maxflow=maxflow;
        _ans=ans;
    }
}

/*
    cin>>n>>m>>S>>T;

    tot=1;
    For(i,1,m){
        int x,y,z,w;
        cin>>x>>y>>z>>w;
        add(x,y,z,w);
    }
*/

const int N=205;
const int dx[]={0,1,0,-1},dy[]={1,0,-1,0};

int n,m,h[N][N],pos[N][N];
int x_0,y_0;

signed main()
{
    cin>>n>>m>>x_0>>y_0;

    For(i,1,n) For(j,1,m) cin>>h[i][j];

    int pc=0;
    For(i,1,n) For(j,1,m) pos[i][j]=++pc;

    int S=2*n*m+1,T=2*n*m+2;

    cpdd::n=2*n*m+2;
    cpdd::S=S;
    cpdd::T=T;
    cpdd::tot=1;

    For(x,1,n){
        For(y,1,m){
            For(i,0,3){
                int tx=x+dx[i],ty=y+dy[i];
                if(tx>=1 && tx<=n && ty>=1 && ty<=m && h[tx][ty]<h[x][y]){
                    cpdd::add(pos[x][y],pos[tx][ty]+n*m,1,h[x][y]-h[tx][ty]);
                }
            }
        }
    }

    For(x,1,n){
        For(y,1,m){
            cpdd::add(S,pos[x][y],1,0);
            cpdd::add(pos[x][y]+n*m,T,1,0);
        }
    }

    int fly,eng;

    cpdd::solve(fly,eng);

    cout<<n*m-fly<<' '<<eng<<endl;

    return 0;
}

完结撒花~