自动搬运

查看原文

来自洛谷，原作者为

	Aventurine_stone （已AFO）愿人生的赌局，赢的总是我们。

搬运于2025-08-24 23:04:31，当前版本为作者最后更新于2024-09-29 19:46:19，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

前言：

我这道题用的 spfa 做的，有人可能会说 spfa 肯定会被后来的 hack 数据卡爆。但是仔细看题会发现，这道题是构造不了菊花图的，那么加上 SLF 优化即可通过此题，当然我又额外加了 LLL 优化，直接跑得飞起。
AC 记录。

1. 题目分析

看到这道题，我首先想到的便是先用 spfa 判一下负环，再在每个网格点上都跑一次 spfa，从而求出最小总权值。但这样时间复杂度肯定爆炸，我们可以反过来想。

2. 题目做法

用 spfa 判负环是不需要的，我们只需要判断网格中相邻的两个值加起来是否小于 $0$ 便可，若有小于 $0$ 的便存在负环。简单证明一下，如果有三个格子，两个负格子中间夹一个正格子，并且两个负数的和的绝对值大于此正数，但每个负数的绝对值都小于此正数，这种情况下，如果想要反复跑这三个点，那么之后的情况便是走一次负格子回过来必定会再跑一次正格子，权值会越跑越大。其他情况也都是这个情况和两数相加是否小于零情况的延伸，证毕。
因为 $q$ 很小，我们只需要以每个人的位置为源点，每个都跑一遍 spfa 即可。然后每个点的总权值都取每个人走到此点的最短距离的最大值。
最后输出所有点的总权值的最小值即可。

3. 代码

#include<bits/stdc++.h>
#define ll long long
int n,m,q,z;
#define pot(x,y) (x-1)*m+y
using namespace std;
const int N=100010,M=400010;
inline int read()
{
	int x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9')
		c=='-'?f=-1:1,c=getchar();
	while(c>='0'&&c<='9')
		x=(x<<1)+(x<<3)+c-'0',c=getchar();
	return x*f;
}
int head[N],ne[M],e[M],w[M],idx;
inline void add(int x,int y,int z)
{
	ne[++idx]=head[x];
	head[x]=idx;
	e[idx]=y,w[idx]=z;
}
int a[N],t;
ll dist[N],mx[N];
bool vis[N];
deque<int>d;
ll sum,num;
void spfa(int x)
{
	for(int i=1;i<=z;i++)
		dist[i]=LONG_LONG_MAX,vis[i]=0;
	dist[x]=0;
	d.push_front(x);
	num=1;
	while(!d.empty())
	{
		t=d.front();
		d.pop_front();
		if(num&&dist[t]>sum/num)//LLL优化 
		{
			d.push_back(t);
			continue;
		}
		sum-=dist[t],num--;
		vis[t]=0;
		for(int i=head[t];i;i=ne[i])
		{
			int c=e[i];
			ll s=dist[t]+w[i];
			if(s<dist[c])
			{
				if(vis[c])
					sum-=dist[c]-s;
				dist[c]=s;
				if(!vis[c])
				{
					vis[c]=1;
					sum+=s,num++;
					if(!d.empty()&&s<=dist[d.front()])//SLF优化 
						d.push_front(c);
					else
						d.push_back(c); 
				}
			}
		}
	}
	for(int i=1;i<=z;i++)
		mx[i]=max(mx[i],dist[i]+a[i]);
}
inline void end()
{
	printf("No");
	exit(0);
}
ll mn;
int x,y;
int main()
{
	n=read(),m=read(),q=read();
	z=n*m;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			t=pot(i,j);
			a[t]=read();
			if(j>1)
			{
				x=pot(i,j-1);
				if(a[x]+a[t]<0)
					end();
				add(t,x,a[t]);
			}
			if(i>1)
			{
				x=pot(i-1,j);
				if(a[x]+a[t]<0)
					end();
				add(t,x,a[t]);
			}
			if(j<m)
				add(t,pot(i,j+1),a[t]);
			if(i<n)
				add(t,pot(i+1,j),a[t]);
		}
	}
	for(int i=1;i<=z;i++)
		mx[i]=-LONG_LONG_MAX;
	while(q--)
	{
		x=read(),y=read();
		spfa(pot(x,y));
	}
	mn=LONG_LONG_MAX;
	for(int i=1;i<=z;i++)
		mn=min(mn,mx[i]);
	printf("%lld",mn);
	return 0;
}