题意

有n个人和m家商店，每个人都要买一道菜。第i个人的坐标是a[i]，第j家商店的坐标是y[i]，有c[i]道菜且每道菜价格为w[i]，每个人还要花费其到商店距离的路费，问最小花费。
$n,m\le 10^5,a[i],y[i],c[i],w[i]\le 10^9$

分析

显然可以费用流做，但跑不过。
考虑把商店和人放到一起按坐标排序，然后从左往右扫，然后不断维护当前的最优解。但当前最优解可能并不是全局最优解，所以还要维护撤销操作。
更具体的讲，对人和商店分别用一个堆来维护，堆中权值表示我要将当前商店或人空置出来并与新加入的人或商店匹配需要付出的最小代价。当新加入一个人时就选择一个最优的商店匹配；新加入一个商店时则尽可能的撤销之前的操作并使答案变得更优。
再加一个小优化，把费用相同的撤销操作放到一起，复杂度就是正确的了。
时间复杂度$O(nlogn)$。

代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<queue>

typedef long long LL;

const int N=100005;
const LL inf=(LL)1e15;

int n,m;
LL a[N],y[N],w[N],c[N],ans;
struct data
{
	LL w,s;
	bool operator < (const data &t) const {return w>t.w;}
};
std::priority_queue<data> A,B;

void ins1(LL x)
{
	LL p=B.top().w,s=B.top().s;
	B.pop();
	ans+=x+p;
	A.push((data){-(x+p)-x,1});
	if (s>1) B.push((data){p,s-1});
}

void ins2(LL y,LL w,LL c)
{
	LL k=0;
	while (!A.empty()&&k<c&&A.top().w+y+w<0)
	{
		LL p=A.top().w,s=A.top().s,f=std::min(c-k,s);
		A.pop();
		s-=f;k+=f;ans+=f*(p+y+w);
		if (s) A.push((data){p,s});
		B.push((data){-(p+y+w)+w-y,f});
	}
	if (k) A.push((data){-y-w,k});
	if (k<c) B.push((data){-y+w,c-k});
}

int main()
{
	scanf("%d%d",&n,&m);
	for (int i=1;i<=n;i++) scanf("%lld",&a[i]);
	LL tot=0;
	for (int i=1;i<=m;i++) scanf("%lld%lld%lld",&y[i],&w[i],&c[i]),tot+=c[i];
	if (tot<n) {puts("-1");return 0;}
	y[0]=-inf;c[0]=inf;
	int i=1,j=0;
	while (i<=n&&j<=m)
	{
		if (a[i]<=y[j]) ins1(a[i]),i++;
		else ins2(y[j],w[j],c[j]),j++;
	}
	while (i<=n) ins1(a[i]),i++;
	while (j<=m) ins2(y[j],w[j],c[j]),j++;
	printf("%lldn",ans);
	return 0;
}

最后

以上就是默默秋天为你收集整理的UOJ #455.【UER #8】雪灾与外卖 堆模拟费用流题意分析代码的全部内容，希望文章能够帮你解决UOJ #455.【UER #8】雪灾与外卖 堆模拟费用流题意分析代码所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。