分糖果(candy)（信息学奥赛一本通- P1380）

【题目描述】

【输入】

【输出】

【输入样例】

4 3 1 2 1 2 2 3 1 4

【输出样例】

5

【提示】

0. 题目概要

有N个小朋友（N<=100,000）和P条好友关系。糖果从起点C开始传递，每一秒传给相邻的朋友。每个人吃糖需要m秒。

求：所有人都吃完糖果的时刻。

核心转化：

1. 所有人吃完的时刻 = max(每个人拿到糖的时刻+m)。

2. 问题转化为：求起点C到其他所有点的最短路径（距离即为时间）。

1. 算法选型

题目中传递时间固定为 1 秒，即所有边权均为 1。

• BFS：无权图最优解，复杂度O(N+P)。

• Dijkstra (邻接表+堆优化)：通用性强，复杂度O(P log N)，本题解采用此方法作为模板练习。

2. 深度解析：为什么不能开 100 亿数组？

这是本题最大的思维陷阱。有同学看到N=10^5，第一反应是：“边数上限M最多可能是完全图 N^2 = 10^10 吗？”

于是反手开了一个 long long vtex[10000000000] —— 虽然这道题没问题，但别的编译器可能将直接导致 MLE或者 CE。

这里要讲一个信奥赛场上的“数据规模跷跷板定律”：

2.1 内存与时间的物理极限

如果真的有10^10条边：

• 内存：10^10*4B *3(数组)约等于120GB。普通比赛限制仅 256MB，根本存不下。

• 时间：光是cin读取100亿个数，就需要好几个小时，而比赛时限通常只有1秒。

2.2 出题人的平衡

在算法题中，N（点）和 M（边）永远是动态平衡的：

• 情形 A：稠密图 (M约等于N^2)

  • 出题人为了不超时，一定会把N限制得很小（通常N<=2000）。

  • 此时才需要考虑邻接矩阵。

• 情形 B：稀疏图 (M与N同量级)

  • 当N达到10^5级别时，出题人必须限制M的大小，通常M只会是N的几倍或几十倍（如2*10^5或 50 *10^5）。

2.3 为什么开100*maxn？

• 常规开2*maxn导致tle，说明测试数据中边数不少（半稠密图）。

• 为了防止数组越界，我们直接开到100*maxn（约 1000 万容量）。

2.4 为什么没炸内存？

• 理论计算：1000 万的int数组*3约等于114MB>64MB。

• 实际情况：利用操作系统的按需分配机制。只要idx指针没有真正推到 1000 万，未使用的数组空间就不会占用物理内存。

• 结果：既防住了边数过多的RE（本题还会造成TLE），又利用系统特性躲过了 MLE。

结论：

看到N=10^5，不要害怕N^2的边数。边数组 (vtex, nxt, wt) 开到 5000000 到 10000000 基本上足够且安全。

3. 完整代码

//点数10^5量级 用Dijkstra #include <iostream> #include <cstring> #include <queue> using namespace std; int n,p,c,m; const int maxn=100010; int h[maxn]; int vtex[100*maxn]; int nxt[100*maxn]; int wt[100*maxn]; int vis[maxn]; int dis[maxn]; int idx; struct node{ int id;//小朋友编号 int w;//到c小朋友的距离 //优先队列默认大根堆，重载运算符修改为小根堆 friend bool operator <(node a,node b){ return a.w>b.w; } }; priority_queue<node> q; void dijkstra(int s){ dis[s]=1;//这个不能丢 node tmp; tmp.id=s; tmp.w=1;//第一秒，糖在1手上，起始就是1秒 q.push(tmp);//起点入队 while(!q.empty()){ tmp=q.top(); q.pop(); int nid=tmp.id; if(vis[nid]==1) continue;//如果tmp已经出队过，就跳过 vis[nid]=1;//如果没有出队过，就打上标记 int p=h[nid]; while(p!=-1){ if(vis[vtex[p]]==0){ if(dis[vtex[p]]>dis[nid]+wt[p]){ dis[vtex[p]]=dis[nid]+wt[p]; q.push({vtex[p],dis[vtex[p]]}); } } p=nxt[p]; } } } void addedge(int u,int v,int w){ vtex[idx]=v; nxt[idx]=h[u]; wt[idx]=w; h[u]=idx++; } int main(){ ios::sync_with_stdio(false); cin.tie(0); cin>>n>>p>>c;//小朋友数 关系数（边数） 起点 cin>>m;//吃糖时间 memset(h,-1,sizeof(h));//初始化头指针数组 //邻接表存图 for(int i=1;i<=p;i++){ int u,v,w; cin>>u>>v; w=1;//小朋友传给小朋友需要1s addedge(u,v,w);//双向的 addedge(v,u,w); } for(int i=1;i<=n;i++) dis[i]=0x3f3f3f3f;//初始化每个小朋友到c小朋友距离为无穷 dijkstra(c); int ma=0; for(int i=1;i<=n;i++){//遍历所有朋友，找最长时间 if(dis[i]!=0x3f3f3f3f) ma=max(ma,dis[i]); } cout<<ma+m;//输出最长传递时间+那个人吃糖果时间 return 0; }