自动搬运

查看原文

来自洛谷，原作者为

	冷月葬T魂 I solemnly swear that I am up to no good

搬运于2025-08-24 22:33:45，当前版本为作者最后更新于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$）：

$$\begin{aligned} & \sum_{i=1}^m(s_{i+1}-t_i) \\ = & \sum_{i=1}^ms_{i+1}-\sum_{i=1}^mt_i \\ = & \sum_{i=1}^ms_{i}-\sum_{i=1}^mt_i \\ = & \sum_{i=1}^m(s_i-t_i) \\ \end{aligned} $$

这是什么？这就是“每条路径的起点与终点海拔之差”的和！
这又是什么？这就是每条路径上走过的“每条边的海拔之差”之和！——即 $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;
}

完结撒花~