P11131 题解

· · 题解

前言：

我这道题用的 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;
}