快速手速题不能犹豫
已知，每个背包最多可以装 件物品。
请你计算，要装下 件物品最少需要多少个背包。
输入格式
一个整数 。
输出格式
一个整数，表示所需背包的最少数量。
数据范围
所有测试点满足 。
输入样例1：
5
输出样例1：
1
输入样例2：
12
输出样例2：
3
代码实现
#include <bits/stdc++.h>
using namespace std;
int n;
int main()
{
cin>>n;
cout<<n/5+(n%5!=0)<<endl;
return 0;
}
单源最短路Dijkstra算法复习
Dijkstra算法的证明
现有的点分为两大集合类：即已经确定最短路的点和还未确定最短路的点
因为Dijktra算法只能处理边的权值为非负的情况，因此初始化时，只能确定源点到源点的最短路为0，并加入已经确定最短路的点的集合中，其余所有点都是还未确定最短路的点。
未确定最短路的点的集合特点是，其前驱都是已经确定最短路的点。因此此时在未确定最短路的点集中选择一个距离最小的点 （这个节点是：没有确定最短路径的节点中距离源点最近的点）其距离记为。那么我们就可以说这个 就是源点到当前这个点 的最短距离。
这里证明用反证法：
假设当前这个距离 不是源点到 的最短路径，那么必然有最短路径为
这里注意，源点到当前点的最短路径一定是从源点 出发的指向 的一条路径，听起来好像是个废话，但是这决定了我们可以不断地寻找当前点的前驱，即最后一个前驱一定是源点。
那么如下图所示， 就是最后一个在未确定最短路的点， 的前驱就是一定在已经确定最短路的点集中的点。
堆优化版Dijkstra算法的模板熟练默写
#include <bits/stdc++.h>
using namespace std;
const int N = 150010, INF = 0x3f3f3f3f;
int h[N],ne[N],e[N],w[N],idx;
bool st[N];
int dist[N];
int n,m;
typedef pair<int,int>PII;
#define x first
#define y second
void add(int a,int b,int c)
{
e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}
void dijkstra()
{
priority_queue<PII,vector<PII>,greater<PII> > heap;
memset(dist,0x3f,sizeof dist);
dist[1]=0;
heap.push({0,1});
while (heap.size())
{
auto t = heap.top();
heap.pop();
int id = t.y;
int distance = t.x;
if (st[id]) continue;
st[id]=true;
for (int i=h[id];~i;i=ne[i])
{
int j = e[i];
if (dist[j]>distance+w[i])
{
dist[j]=distance+w[i];
heap.push({dist[j],j});
}
}
}
}
int main()
{
scanf("%d%d",&n,&m);
memset(h,-1,sizeof h);
while (m--)
{
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
add(a,b,c);
}
dijkstra();
if (dist[n]==INF) puts("-1");
else printf("%d\n",dist[n]);
return 0;
}
结合周赛题目具体运用
给定一个 个点 条边的不含重边和自环的无向图。
点的编号为 ，边的编号为 。
在 时刻，你位于 号点。
你的任务是尽可能早的抵达 号点。
第 条边连接点 和点 ，通过此边需要花费的时间为 。
在整个移动过程中，你只有在整数时刻才能离开某一点前往另一点。
此外，第 个点有 个禁止离开时刻。
在每个点的禁止离开时刻，你无法离开该点前往其它点。
请你计算抵达 号点的最早可能时刻。
输入格式
第一行包含两个整数 。
接下来 行，其中第 行包含三个整数 ，表示第 条边连接点 和 ，通过此边需要花费的时间为 。
接下来 行，其中第 行首先包含一个整数 ，表示第 个点有 个禁止离开时刻，随后包含 个互不相同的升序排序的整数 ，表示所有禁止离开时刻。
输出格式
一个整数，表示抵达 号点的最早可能时刻。
如果无法抵达 号点，则输出 -1。
数据范围
前 个测试点满足 。
所有测试点满足 ，，，，，，，所有 相加之和不超过 。
输入样例1：
4 6
1 2 2
1 3 3
1 4 8
2 3 4
2 4 5
3 4 3
0
1 3
2 3 4
0
输出样例1：
7
样例1解释
从点 到点 ，考虑如下三条路线：
- 在时刻 通过第 条边离开点 ，并于时刻 抵达点 。
- 在时刻 通过第 条边离开点 ，并于时刻 抵达点 ，由于点 在时刻 禁止离开，所以在时刻 通过第 条边离开点 ，并于时刻 抵达点 。
- 在时刻 通过第 条边离开点 ，并于时刻 抵达点 ，在时刻 通过第 条边离开点 ，并于时刻 抵达点 。
最佳方案为第三条路线，抵达点 的最早可能时刻为 。
输入样例2：
3 1
1 2 3
0
1 3
0
输出样例2：
-1
- 越早到当前点，那么就是越早从这个点离开。那么我们就可以只维护到当前点最短的时刻即可。因为无论这个点是否会有禁止的时刻显示，越早到这个点，总是会比晚到这个点尽早地从此点离开出发到下一个点的。
- 其实问题实现了转化，对于当前这个点，只需要检验一下和这个点禁止开始的时刻的关系即可，我们要找的就是大于等于 的且不在当前点的禁止开始的时刻中的值。
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int>PII;
#define x first
#define y second
const int N = 100010, M = 2*N, INF = 0x3f3f3f3f;
int h[N],e[M],ne[M],w[M],idx;
int dist[N];
vector<int>delay[N];
bool st[N];
int n,m;
int add_delay(int id,int distance) // 对于每个id的delay数组，去枚举即可
{
for (auto t:delay[id])
{
if (t==distance) distance++;
else if (t>distance) break;
}
return distance;
}
void add(int a,int b,int c)
{
e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}
void dijkstra()
{
priority_queue<PII,vector<PII>,greater<PII> >heap;
memset(dist,0x3f,sizeof dist);
dist[1]=0;
heap.push({0,1});
while (heap.size())
{
auto t = heap.top();
heap.pop();
int id = t.y;
if (st[id]) continue;
st[id]=true;
int distance = add_delay(id,t.x);
for (int i=h[id];~i;i=ne[i])
{
int j = e[i];
if (dist[j]>distance+w[i])
{
dist[j]=distance+w[i];
heap.push({dist[j],j});
}
}
}
}
int main()
{
scanf("%d%d",&n,&m);
memset(h,-1,sizeof h);
while (m--)
{
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
add(a,b,c),add(b,a,c);
}
for (int i=1;i<=n;i++)
{
int cnt;
scanf("%d",&cnt);
delay[i].resize(cnt);
for (int j=0;j<cnt;j++)
scanf("%d",&delay[i][j]);
}
dijkstra();
if (dist[n]==INF) puts("-1");
else printf("%d\n",dist[n]);
return 0;
}
Floyd多源最短路算法证明复习
floyd算法的第一层循环k，即从i出发，到j，且现在只用到了编号为1~k的节点。
即循环到k时，即可求出现在用1~k号节点，图中任意两点的最短距离。
floyd算法应用为：
- 求多源最短路
- 求传递闭包
- 找最小环（找正权图中，价值和最小的环）
- 求恰好经过k条边的最短路，倍增思想
的思想
- 状态表示：定义一个 表示从i出发，走到j，且用到的节点不超过k的路径
- 状态属性：求路径中的最小值
- 状态计算：所有的路径集合分为两大类，一类是不经过节点k，一类是经过节点k。那么不经过节点k的路径为 ；经过节点k的路径为
Floyd模板复习
#include <bits/stdc++.h>
using namespace std;
const int N = 210;
int dist[N][N];
int n,m,k;
int main()
{
cin>>n>>m>>k;
// 没有边的初始化为无穷，自身到自身的距离为0
memset(dist,0x3f,sizeof dist);
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
if (i==j)
dist[i][j]=0;
while (m--)
{
int a,b,c;
cin>>a>>b>>c;
dist[a][b]=min(dist[a][b],c);
}
for (int k=1;k<=n;k++)
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j]);
while (k--)
{
int a,b;
cin>>a>>b;
// 这里不能写成dist[a][b]==0x3f3f3f3f，因为要考虑搭到负权边的存在
if (dist[a][b]>=0x3f3f3f3f/2) puts("impossible");
else cout<<dist[a][b]<<endl;
}
return 0;
}
结合具体题目，对Floyd的k的深层理解
给定一个 个点的加权有向图，点的编号为 。
图中任意两点之间都有两条方向相反的边连接两点。
从点 到点 的边的长度为 。
给定一个 的排列 。
你需要对该图依次进行 个操作。
其中，第 个操作是将点 以及该点的所有入边和出边从图中移除。
在执行每一个操作之前，你还需要进行如下计算：
- 对于每个当前剩余点对 ，计算从点 到点 的最短路长度。
- 将这些最短路长度全部相加得到最短路之和。
注意：
- 剩余点对 ：两个还未被移除的点 （）组成的点对。
- 和 是两个不同点对，需分别计算最短路长度并计入最短路之和。
- 个操作是按顺序依次执行的，前面的操作会对后面的计算产生影响。
请你输出执行每个操作前计算得到的最短路之和。
输入格式
第一行包含整数 。
接下来 行，每行包含 个整数，其中第 行第 个数为 。
最后一行包含 个整数 。
输出格式
共一行，输出 个整数，其中第 个整数表示执行第 个操作之前，计算得到的最短路之和。
数据范围
前 个测试点满足 。
所有测试点满足 ，，，，保证 是一个 的排列。
输入样例1：
1
0
1
输出样例1：
0
输入样例2：
2
0 5
4 0
1 2
输出样例2：
9 0
输入样例3：
4
0 3 1 1
6 0 400 1
2 4 0 1
1 1 1 0
4 1 2 3
输出样例3：
17 23 404 0
题目分析
我们每次尝试求删除点和这点的入边与出边并不好做，想想就很复杂。但是这时候可以转化一下思想，即从后往前依次添加点，去等价从前往后依次删除点。
即对于给定的待删除的 的排列，如果按正序求解，即先求n个点情况下，所有点对的最短路径之和，再求n-1个点情况下...，那么我们转化之后，就是从后往前先添加这个点，然后在只用节点编号不超过这个点的情况下的点对的最小路径之和。那么我们通过倒序添加点求解，再正序输出结果，就实现了正序删除点的效果。
#include <bits/stdc++.h>
using namespace std;
const int N = 510;
int dist[N][N];
int n;
int path[N];
bool st[N];
long long ans[N];
int main()
{
cin>>n;
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
cin>>dist[i][j];
for (int i=1;i<=n;i++)
cin>>path[i];
for (int u=n;u>=1;u--)
{
int k=path[u];
st[k]=true;
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j]);
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
{
if (st[i]&&st[j])
ans[u]+=dist[i][j];
}
}
for (int i=1;i<=n;i++)
cout<<ans[i]<<" ";
return 0;
}