【题目链接】
ybt 1380：分糖果(candy)
可以认为小朋友间关系的最大数量为
1
0
5
10^5
105
【题目考点】
1. 图论：广搜
2. 图论：最短路径
【解题思路】
每个小朋友是一个顶点，朋友间的关系是边，糖果从每个人传到另一个人都是1秒钟的时间，因而该图是无向无权图。
假设一位小朋友A接收糖果的时刻是t，那么与该小朋友有关系的小朋友接收到糖果的时刻是t+1。由于每个小朋友吃糖的时间都是m，因而该小朋友A把糖吃完的时刻是t+m。
解法1：广搜
队列中保存的是结点，结点包括属性：小朋友编号，收到糖的时刻。一开始把结点“小朋友C在第1秒收到糖”加入队列，每次出队直到队空。把出队的小朋友u的所有有关系的未收到糖的小朋友v收到糖的时间为u收到糖的时间加1。构成结点，再入队。题目所求的结果为每个小朋友吃完糖时间的最大值。
复杂度：
O
(
V
+
E
)
O(V+E)
O(V+E)
解法2：求单源最短路径
可以把无权图当做每条边权值为1的带权图。
求从小朋友C出发的单源最短路径，顶点A到顶点B的路径即为将糖果从A传到B的时间。这样就可以得到每个小朋友接收到糖果的时间，加上m后即为每个小朋友吃完糖果的时间。求所有小朋友吃完糖果的时间的最大值。文章来源：https://www.toymoban.com/news/detail-402581.html
关于数据量：由于顶点数n达到 1 0 5 10^5 105，边数最大为 O ( 1 0 10 ) O(10^{10}) O(1010)，当然题目不会给出这么大数量的边，否则做输入的时间都不够。如果假定边的数量最大为 1 0 5 10^5 105，那么可以选择Dijkstra堆优化算法 O ( E l o g E ) O(ElogE) O(ElogE)和SPFA算法 O ( k E ) O(kE) O(kE)。文章来源地址https://www.toymoban.com/news/detail-402581.html
【题解代码】
解法1：广搜算法
#include <bits/stdc++.h>
using namespace std;
#define N 100005
struct Node
{
int v, t;//v:顶点编号 t:糖果到达该顶点的时间
Node(){}
Node(int a, int b):v(a), t(b){}
};
int n, p, c, m, mxTime;//mxTime：所有小朋友中吃完糖果时间的最大值
vector<int> edge[N];
bool vis[N];//vis[i]：顶点i是否已分过糖果
void bfs(int sv)
{
queue<Node> que;
vis[sv] = true;
que.push(Node(sv, 1));
while(que.empty() == false)
{
Node u = que.front();
que.pop();
mxTime = max(mxTime, u.t+m);//接收糖果时间为u.t的小朋友，吃完糖的时间为u.t+m
for(int v : edge[u.v])
{
if(vis[v] == false)
{
vis[v] = true;
que.push(Node(v, u.t+1));
}
}
}
}
int main()
{
int f, t;
cin >> n >> p >> c >> m;
for(int i = 1; i <= p; ++i)
{
cin >> f >> t;
edge[f].push_back(t);
edge[t].push_back(f);
}
bfs(c);
cout << mxTime;
return 0;
}
解法2：Dijkstra堆优化算法
#include <bits/stdc++.h>
using namespace std;
#define N 100005
#define INF 0x3f3f3f3f
struct Pair
{
int u, d;//u:顶点 d:距离
Pair(){}
Pair(int a, int b):u(a),d(b){}
bool operator < (const Pair &b) const//优先队列中 d更小的更优先
{
return b.d < d;
}
};
int n, p, c, m, mxTime;//mxTime：顶点c单源最短路径中的最大值，即传递时间的最大值
vector<int> edge[N];
bool vis[N];//vis[i]：顶点i是否在队列中
int dis[N];//dis[i]：糖从起点传到顶点i的时间
void dijkstra(int sv)//sv起始点
{
priority_queue<Pair> pq;//优先队列中 d更小的更优先
memset(dis, 0x3f, sizeof(dis));//dis初始值为INF
dis[sv] = 0;
pq.push(Pair(sv, 0));
while(pq.empty() == false)
{
int u = pq.top().u;
pq.pop();
if(vis[u])//如果顶点u已经访问过，则跳过
continue;
vis[u] = true;
for(int v : edge[u])
{
if(vis[v] == false && dis[v] > dis[u]+1)
{
dis[v] = dis[u]+1;
pq.push(Pair(v, dis[v]));
}
}
}
}
int main()
{
int f, t;
cin >> n >> p >> c >> m;
for(int i = 1; i <= p; ++i)
{
cin >> f >> t;
edge[f].push_back(t);
edge[t].push_back(f);
}
dijkstra(c);
for(int i = 1; i <= n; ++i)
if(dis[i] != INF && mxTime < dis[i])
mxTime = dis[i];
cout << 1+mxTime+m;//起始位置时间为1，传到最后一个接收的小朋友的时间为1+mxTime，吃糖用m时间，吃完时间为1+mxTime+m
return 0;
}
解法3：SPFA算法
#include <bits/stdc++.h>
using namespace std;
#define N 100005
#define INF 0x3f3f3f3f
int n, p, c, m, mxTime;//mxTime：顶点c单源最短路径中的最大值，即传递时间的最大值
vector<int> edge[N];
bool vis[N];//vis[i]：顶点i是否在队列中
int dis[N];//dis[i]：糖从起点传到顶点i的时间
void spfa(int sv)
{
memset(dis, 0x3f, sizeof(dis));
queue<int> que;
que.push(sv);
vis[sv] = true;
dis[sv] = 0;
while(que.empty() == false)
{
int u = que.front();
que.pop();
vis[u] = false;
for(int v : edge[u])
{
if(dis[v] > dis[u]+1)
{
dis[v] = dis[u]+1;
if(vis[v] == false)
{
que.push(v);
vis[v] = true;
}
}
}
}
}
int main()
{
int f, t;
cin >> n >> p >> c >> m;
for(int i = 1; i <= p; ++i)
{
cin >> f >> t;
edge[f].push_back(t);
edge[t].push_back(f);
}
spfa(c);
for(int i = 1; i <= n; ++i)
if(dis[i] != INF && mxTime < dis[i])
mxTime = dis[i];
cout << 1+mxTime+m;//起始位置时间为1，传到最后一个接收的小朋友的时间为1+mxTime，吃糖用m时间，吃完时间为1+mxTime+m
return 0;
}
到了这里，关于信息学奥赛一本通 1380：分糖果(candy)的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
