自动搬运

查看原文

来自洛谷，原作者为

	yyyyxh OI 是啥 (O_o)？

搬运于2025-08-24 22:18:51，当前版本为作者最后更新于2023-10-12 15:02:40，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

wssb，感谢 zhy 指教。

提供一个简单得多的做法：每个格子只会被两条来自不同方向的对角线覆盖，考虑把每个格子看成一条边，问题转换成了二分图最小权点覆盖问题。这是经典网络流问题，最小割建模可以拿到 40 分。

观察一下连边的形式，我们对于格子 $(i,j)$ 定义 $x=i+m-j,y=i+j-1$，那么这个格子会对左部的 $x$ 与右部的 $y$ 连边。

推推式子，可以得到 $(x,y)$ 有连边当且仅当：

且要求 $x+y+m$ 是奇数。

将原图按照奇偶分类后就变成了如下问题：对于每一个左部点，向右部点的一个区间连边，求最大流。

这个问题十分经典，我们考虑直接贪心：按照右端点排序，每次选择最靠近左端点的流。这个可以用并查集维护。

按照右端点排序可以用计数排序做到 $O(n)$，所以总时间复杂度可以做到 $O(n\alpha(n))$。

这里是 $O(n\log n)$ 直接 sort 的代码：

#include <cstdio>
#include <algorithm>
using namespace std;
int read(){/*...*/}
typedef long long ll;
const int N=400003;
int n,m,rk,tp;
int a[N],b[N];
int val[N];
struct seq{
	int l,r,x;
	friend bool operator<(const seq a,const seq b){
		return a.r<b.r;
	}
}s[N];
int f[N];
int rt(int x){
	if(f[x]==x) return x;
	return f[x]=rt(f[x]);
}
ll solve(){
	for(int i=1;i<=rk+1;++i) f[i]=i;
	sort(s+1,s+tp+1);
	ll sum=0;
	for(int i=1;i<=tp;++i){
		while(rt(s[i].l)<=s[i].r&&s[i].x){
			int p=rt(s[i].l);
			int t=min(val[p],s[i].x);
			s[i].x-=t;val[p]-=t;
			sum+=t;
			if(!val[p]) f[p]=p+1;
		}
	}
	return sum;
}
int main(){
	n=read();m=read();
	for(int i=1;i<n+m;++i) a[i]=read();
	for(int i=1;i<n+m;++i) b[i]=read();
	ll res=0;
	for(int p=1,t=m&1;;p^=1,t^=1){
		tp=rk=0;
		for(int i=p?1:2;i<n+m;i+=2){
			int l=max(m+1-i,1-m+i);
			int r=min(n+n+m-1-i,i+m-1);
			if((l&1)!=t) ++l;
			if((r&1)!=t) --r;
			l=(l+1)>>1;
			r=(r+1)>>1;
			if(l<=r){++tp;s[tp].l=l;s[tp].r=r;s[tp].x=a[i];}
		}
		for(int i=t?1:2;i<n+m;i+=2) val[++rk]=b[i];
		res+=solve();
		if(!p) break;
	}
	printf("%lld\n",res);
	return 0;
}