关键词：
描述
John计划为他的牛场建一个围栏，以限制奶牛们的活动。他有N种可以建造围栏的木料，长度分别是l1,l2…lN，每种长度的木料无限。修建时，他将把所有选中的木料拼接在一起，因此围栏的长度就是他使用的木料长度之和。但是聪明的John很快发现很多长度都是不能由这些木料长度相加得到的，于是决定在必要的时候把这些木料砍掉一部分以后再使用。不过由于John比较节约，他给自己规定：任何一根木料最多只能削短M米。当然，每根木料削去的木料长度不需要都一样。不过由于测量工具太原始，John只能准确的削去整数米的木料，因此，如果他有两种长度分别是7和11的木料，每根最多只能砍掉1米，那么实际上就有4种可以使用的木料长度，分别是6, 7, 10, 11。
Clevow是John的牛场中的最聪明的奶牛，John请她来设计围栏。Clevow不愿意自己和同伴在游戏时受到围栏的限制，于是想刁难一下John，希望John的木料无论经过怎样的加工，长度之和都不可能得到她设计的围栏总长度。
不过Clevow知道，如果围栏的长度太小，John很快就能发现它是不能修建好的。因此她希望得到你的帮助，找出无法修建的最大围栏长度。
格式
输入格式
输入的第一行包含两个整数N, M (1<N<100, 0<=M<3000)，分别表示木料的种类和每根木料削去的最大值。以下各行每行一个整数li(1<li<3000),表示第i根木料的原始长度。
输出格式
输出仅一行，包含一个整数，表示不能修建的最大围栏长度。如果任何长度的围栏都可以修建或者这个最大值不存在，输出-1。
样例1
样例输入1
2 1
7
11
样例输出1
15
对问题进行转换
在modl[1]的剩余系下，我们设dis[i]表示i=modl[1]的最小的体积
那么如果dis[i]可以到达, 那么dis[i]+l[1]*k(k=0~无限大)都是可以到达的。
初始的时候dis[0]=0,因为l[1]%l[1]=0,并且如果等于l[1]的话后面的点一定要对其进行松弛而实际上不需要。
于是我们通过mod对每一个点进行松弛，
答案就是根据定义的最小体积减去l[1],因为modl[1]
判断无解的情况
1.最小的是1, 那么所有的点都可以以1进行松弛，那么所有的点都可以到达。
2.有一个余数不能到达，那么他的 dis[i]+l[1]*k(k=0~无限大)也都是不能到达的。
于是我们在求最短路的时间复杂度内解决了这个问题
spfa o(n^2) dij(nlgn)
#include<bits/stdc++.h>
using namespace std;
int dis[30000],book[30000],l[30000],n,m,ans,a[30000],vis[30000],cnt=0;
int spfa()
{
memset(book,0,sizeof(book));memset(dis,36,sizeof(dis));
int inf=dis[1];dis[0]=0;book[0]=1;
queue<int> q;q.push(0);
while(!q.empty())
{
int x=q.front();q.pop();book[x]=0;
for(int i=2;i<=cnt;i++)
{
if(dis[x]+l[i]<dis[(x+l[i])%l[1]])
{
dis[(x+l[i])%l[1]]=dis[x]+l[i];
if(!book[(x+l[i])%l[1]])
book[(x+l[i])%l[1]]=1,q.push((x+l[i])%l[1]);
}
}
}
for(int i=0;i<l[1];i++) if(dis[i]==inf) return -1;
int ans=0;
for(int i=0;i<l[1];i++) ans=max(ans,dis[i]-l[1]);
return ans;
}
main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
for(int j=a[i]-m;j<=a[i];j++)if(j>=1) vis[j]=1;
}
if(vis[1]){cout<<"-1
";return 0;}
for(int i=1;i<=3000;i++)if(vis[i])l[++cnt]=i;
printf("%d",spfa());
return 0;
}
分层图最短路（dp思想）bzoj2662[beijingwc2012]冻结
2662:[BeiJingwc2012]冻结TimeLimit:3Sec MemoryLimit:128MBSubmit:999 Solved:535[Submit][Status][Discuss]Description “我要成为魔法少女！” “那么，以灵魂为代价，你希望得到什么？”“我要将有关魔法和奇迹的 查看详情
bzoj2662:[beijingwc2012]冻结最短路建图
好久没有1A题啦?(^?^*)一个sb建图，我居然调样例调了10min看起来是双向边，其实在建图的时候要当成有向图，否则他会时间倒流（233）把每个点裂成k个点，然后把每条边裂成4条边（正向反向&膜不膜）（话说我好像不会用openliv... 查看详情
[vijos2024]无向图最短路径
Description无向图最短路径问题，是图论中最经典也是最基础的问题之一。本题我们考虑一个有$n$个结点的无向图$G$。$G$是简单完全图，也就是说$G$中没有自环，也没有重边，但任意两个不同的结点之间都有一条带权的双向边。每... 查看详情
p2662牛场围栏同余最短路(代码片段)
链接：https://www.luogu.com.cn/problem/P2662 题目要求求出最大不能拼凑出来的木板长度，因此我们把最短的木板作为剩余系，扫描其他的木板并建边。题目另外说每个木板可以最多截掉m米，那么只要再扫描到每个木板的时候依次扫... 查看详情
p2662牛场围栏同余最短路(代码片段)
链接：https://www.luogu.com.cn/problem/P2662 题目要求求出最大不能拼凑出来的木板长度，因此我们把最短的木板作为剩余系，扫描其他的木板并建边。题目另外说每个木板可以最多截掉m米，那么只要再扫描到每个木板的时候依次扫... 查看详情
hdu3499(分层图最短路or反向建图)(代码片段)
传送门方法一：分层图#include<bits/stdc++.h>#defineper(i,a,b)for(inti=a;i<=b;i++)#definemod1000000007usingnamespacestd;typedeflonglongll;constllinf=23333333333333333LL;constdoubleeps=1e-8;intT;intread() 查看详情
bzoj2662冻结
分层图最短路。#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<queue>#definemaxk55#definemaxv5050#definemaxe5000050#defineinf2147483647usingnamespa 查看详情
小雨坐地铁分层图最短路(代码片段)
思路 如果考虑暴力建图的方法 对于每一条线路的每一个站点可到达的站点建边 在每条线路有1e5个站点的条件下显然是不现实的 如何解决建图的问题是此题的关键 因为有转车和车费逐步增加... 查看详情
p1354房间最短路问题(建图&最短路)(代码片段)
P1354房间最短路问题(建图&最短路)建图跑最短路就行了，两点加边时特判下是否有墙挡住了。这里用floyd就可以过了//Problem:P1354房间最短路问题//Contest:Luogu//URL:https://www.luogu.com.cn/problem/P1354//MemoryLimit:125MB//TimeLimit:1000ms//Date:2... 查看详情
hdu-5786（补图最短路）
...m条边，由一个s出现的单源最短路解题思路：首先，暴力建图不行，点太多，那么我们就按照它的规则来，把m条边建好，但是建的这个图表示不走的方法，然后我们需要用一个东西来保存去除这些直接相连的边的其它点，用set代... 查看详情
同余最短路(总结)(代码片段)
同余最短路(总结)同余最短路其实是一种优化最短路建图的方法。通常是解决给定m个整数，求这m个整数能拼凑出多少的其他整数(这m个整数可以重复取)或给定m个整数，求这m个整数不能拼凑出的最小（最大）的整... 查看详情
bzoj2662
题解：spfa最短路径dp[i][j]表示到i，用了j掌权然后转移代码：#include<bits/stdc++.h>usingnamespacestd;constintN=105;intn,m,k,in1,in2,in3,f[N][N],ans=1e9,used[N];vector<pair<int,int>>graph[N];queue<int> 查看详情
p4568[jloi2011]飞行路线&&分层图最短路板子(代码片段)
...最后的答案就是每一个n,n‘,n‘‘...中取一个最大值.怎么建图：用手建图for(inti=1,a,b,d;i<=m;i++)a=read(),b=read(),d=read();add(a,b,d),add(b,a,d);//在原图上连边for(intj=1;j<=k;j++)add(a+(j-1)*n,b+j*n,0);//两层之间的连一条无边权的边add(b+(j-1)*n,a+j*n... 查看详情
图论-虚拟节点分层建图
图论-虚拟节点分层建图Nya图最短路题目链接:VirtualJudgeAcwing题意:题解:$a,b$连一个$w$的边,是正常操作,这里有一个重要操作是$a$层和$a+1$层能直接传送,如果这里使用笨笨的建图方式,那么时间复杂度就是$O(n^2)$,时间复杂度太高,不太... 查看详情
p1629邮递员送信最短路+反向建图(代码片段)
...其实考虑回来的时候有最短路，那么意味着我们反向建图跑一下的最短路，就是回来的最短路。#include<bits/stdc++.h>u 查看详情
codeforces786b(区间图最短路)(代码片段)
...区间,一个区间可以用线段树表示为$log(n)$个点,这样就把建图时间压缩成$mlogn$了,然后跑最短路就行了。查看代码#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;constintmaxn=4e6+5;constintmod=1e9+7;constllinf=0x3f3f3f3f3f3f3f3f;llqpow(lla,llb)llres=... 查看详情
图最短路径？
】图最短路径？【英文标题】：Graphshortestpath?【发布时间】：2012-07-2209:51:47【问题描述】：我正面临着我认为是图上的一种最短路径问题。我需要找到从节点A到B的最短路径，考虑到所有边对于连接的顶点具有正权重，对于未连... 查看详情
p4568飞行路线分层图最短路(代码片段)
P4568飞行路线分层图最短路分层图最短路问题模型求最短路时，可有\(k\)次更改边权（减为0）思路在普通求\(Dijkstra\)基础上，\(dis[x][j]\)多开一维\(j\)以存已用了多少次机会，然后每次松弛时，做完普通松弛操作后，还要使用一次... 查看详情