题解：P7863 「EVOI-RD1」飞鸟和蝉

· · 题解

喜报！没有算边数导致该题 100\rightarrow30。/ll
衷心祝愿大家不再重蹈覆辙。

Solution

看到这玩意儿一眼费用流。又要跳的次数最小，又要花费最小。然后注意到如果按照高低关系进行建图，喜提 DAG，然后从高处一直往低处走这个过程其实就是 DAG 上的一条路径。那这不就是 DAG 最小路径覆盖吗？

好的，第一问我们解决了，我们要在算第一问的过程中顺手给第二问解决了。我们注意一下某种路径覆盖方案下的最小花费。注意到如果有 k 条链，就必须进行 k 次从某条链的尾部跳到另一条链（可以是自己）的头部，花费为头部的高度减去尾部的高度，我们给他全部合并一下，就能发现某种路径覆盖方案下最小花费就是某条链的头部高度减去尾部高度。我们能否把其转化到边的费用上？可以的可以的。可以参考一下下面这张图：

:::success[code]


#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=5005;
struct node{int u,v,w,c;};
int n,m,h[55][55],s,t=N-4,flag[N],dis[N],ans,x,y;
bool pd[N];
int fx[]={0,1,0,-1,0};
int fy[]={0,0,1,0,-1};
bool vis[N];
vector<node> edges;
vector<int> e[N];
queue<int> q;
int f(int i,int j){return (i-1)*m+j;}
bool check(int i,int j){
    if(!i||!j||i>n||j>m) return 0;
    return 1;
}
void add(int u,int v,int w,int c){
    edges.push_back({u,v,w,c});
    edges.push_back({v,u,0,-c});
    e[u].push_back(edges.size()-2);
    e[v].push_back(edges.size()-1);
}
bool SPFA(){
    memset(dis,0x3f,sizeof dis);
    dis[s]=0,q.push(s);
    while(!q.empty()){
        int u=q.front();q.pop();
        vis[u]=0;
        for(auto to:e[u]){
            int v=edges[to].v;
            if(dis[v]>dis[u]+edges[to].c&&edges[to].w){
                dis[v]=dis[u]+edges[to].c;
                if(!vis[v]) q.push(v),vis[v]=1;
            }
        }
    }
    return dis[t]<1e18;
}
int dfs(int u,int flow){
    if(u==t) return flow;
    int sum=0;
    vis[u]=1;
    for(int i = flag[u];i<e[u].size();i++){
        flag[u]=i;
        int v=edges[e[u][i]].v;
        if(!vis[v]&&dis[v]==dis[u]+edges[e[u][i]].c&&edges[e[u][i]].w){
            int tmp=dfs(v,min(flow,edges[e[u][i]].w));
            edges[e[u][i]].w-=tmp,edges[e[u][i]^1].w+=tmp,flow-=tmp,sum+=tmp,ans+=edges[e[u][i]].c*tmp;
            if(!flow) break;
        }
    }
    vis[u]=0;
    if(!sum) dis[u]=-1;
    return sum;
}
int dinic(){
    int ans=0;
    while(SPFA()){
        memset(flag,0,sizeof flag);
        ans+=dfs(s,1e9);
    }
    return ans;
}
signed main(){
    cin>>n>>m>>x>>y;
    for(int i = 1;i<=n;i++)
        for(int j = 1;j<=m;j++)
            cin>>h[i][j],add(s,f(i,j),1,0),add(f(i,j)+n*m,t,1,0);
    for(int i = 1;i<=n;i++)
        for(int j = 1;j<=m;j++)
            for(int k = 1;k<=4;k++)
                if(check(i+fx[k],j+fy[k])&&h[i][j]>h[i+fx[k]][j+fy[k]])
                    add(f(i,j),f(i+fx[k],j+fy[k])+n*m,1,h[i][j]-h[i+fx[k]][j+fy[k]]);
    cout<<n*m-dinic()<<' ';
    cout<<ans;
    return 0;
}