Luogu2662 牛场围栏（最短路）

　　小凯的疑惑升级版的升级版。答案若存在不会超过3000²-3000，暴力dp似乎勉强可以过。当然这不优美。

　　注意到如果能拼出长度为l的围栏，就一定能拼出长度为l+kx的围栏，其中x为最短的（或任意一个）围栏长度。这样将值域范围缩小到了3000以内。于是将同余类间连长为木料长度的边，求出0为源点到每个点的最短路（据说spfa有奇效），答案即为max{dis}-x。

　　这个东西就叫同余最短路。

#include<iostream> 
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
int read()
{
    int x=0,f=1;char c=getchar();
    while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
    while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
    return x*f;
}
#define N 110
#define M 3010
int n,m,a[N],q[M],d[M],f[M][M],p[M],t=0,P=3000,ans;
bool flag[M];
struct data{int to,nxt,len;
}edge[M*M];
void addedge(int x,int y,int z){t++;edge[t].to=y,edge[t].nxt=p[x],edge[t].len=z,p[x]=t;}
int inc(int &x){x++;if (x>P+1) x-=P+1;return x;}
void spfa()
{
    memset(flag,0,sizeof(flag));
    memset(d,42,sizeof(d));d[0]=0;
    int head=0,tail=1;q[1]=0;
    do
    {
        int x=q[inc(head)];flag[x]=0;
        for (int i=p[x];i;i=edge[i].nxt)
        if (d[x]+edge[i].len<d[edge[i].to])
        {
            d[edge[i].to]=d[x]+edge[i].len;
            if (!flag[edge[i].to])
            {
                q[inc(tail)]=edge[i].to;
                flag[edge[i].to]=1;
            }
        }
    }while (head!=tail);
}
int main()
{
#ifndef ONLINE_JUDGE
    freopen("cow.in","r",stdin);
    freopen("cow.out","w",stdout);
    const char LL[]="%I64d
";
#else
    const char LL[]="%lld
";
#endif
    n=read(),m=read();
    for (int i=1;i<=n;i++)
    {
        a[i]=read(),P=min(P,max(a[i]-m,1));
        for (int j=max(1,a[i]-m);j<=a[i];j++)
        flag[j]=1;
    }
    for (int i=0;i<P;i++)
        for (int j=1;j<=3000;j++)
        if (flag[j]) addedge(i,(i+j)%P,j);
    spfa();
    for (int i=0;i<P;i++)
    ans=max(ans,d[i]-P);
    cout<<(ans==0?-1:ans);
    return 0;
}