我自己平时刷信奥题有个习惯每天打卡一道P开头的老题慢慢把USACO这类经典题库啃下来。前两天刷到USACO 15年1月赛季的 Meeting Time S题目编号P3116卡了我将近一个下午。这题表面看就是“两头牛从同一个起点出发最后在终点会合求最早能同时到达的时间”一上来很容易想成最短路问题结果怎么写怎么错。搞清楚之后才发现它其实是比较经典的DAG上集合DP非常适合用来理解“为什么有些题不能只存最优值”。这篇文章我就把完整思路、C实现和调试细节都拆出来给同样被这题折磨过的同学参考。无论是刷USACO还是准备信息学竞赛这类题都值得多花点时间做透。题目里的N给得不大数据范围看起来温和但算法思想非常典型一张有向无环图每个转移带两个不同的时间求两条路径在终点的时间交集最小值。听起来简单实际写起来有挺多细节尤其是状态设计选错思路就是一路WA。1. 题意拆解两头牛从同一扇门出发怎样才算“同时见面”1.1 一条边、两个时间读完题先明确模型题目先给你N个点、M条有向边。每条有向边同时给出两个整数时间第一个是Bessie走这条路的用时第二个是Elsie走这条路的用时。两头牛都从1号点出发目的地都是N号点沿有向边移动最终在N号点碰头。注意它们不是约定好走同一条路而是各走各的早到的牛需要在终点等另一头牛。所以核心目标变成找到一对路径Bessie走完用时TElsie走完用时也是T然后让这个T尽量小。这个地方很多人一开始会把模型理解偏以为两头牛必须走完全相同的路或者以为只要有向图上两条最短路的时间凑巧相等就行。都不对。题目只要求“同时到达N”并没有限制路径是否相同两条牛可以走完全不同的路线只要最终时间相等。另外还有一个隐含条件图是DAG也就是有向无环图。这个条件非常关键。正因为无环路径条数和路径长度才有明确上界也才能用拓扑序做动态规划。如果图里有环问题会变得复杂得多根本不是这道题想考你的东西。1.2 为什么“各走各的最短路径”完全不成立我一开始的想法特别朴素分别对Bessie和Elsie求一次从1到N的最短路看两个最短路时间是否相等如果不相等就输出IMPOSSIBLE。试了一下样例都过不了细想就发现错得离谱。举个例子。假设图里有两条路路线11 - 2 - 4其中1-2的Bessie用时是1Elsie用时是1002-4两头牛都是10。路线21 - 3 - 4其中1-3的Bessie用时是2Elsie用时是23-4两头牛都是10。那么Bessie走路线1用时11走路线2用时12Elsie走路线1用时110走路线2用时12。Bessie的最短时间是11Elsie的最短时间是12如果只记最短时间你会觉得两头牛永远不能同时到达输出IMPOSSIBLE。但实际上Bessie也可以选择走路线2用时12和Elsie正好同时到达。答案应该是12。问题出在哪出在“每个点只保留最早到达时间”这件事上。Bessie到达点4既可以走11那条路也可以走12那条路如果只保留11就把12这个可能性弄丢了。而恰恰是12这个“非最优”时间才是两头牛共同的时间。所以这道题给我们的第一个教训就是当题目要求的是“两条路径的时间完全相等”时你不能只关心每个点的最小值你得知道每个点“所有可能到达的时间”。这是一个典型的集合DP题不是最短路题。1.3 题目范围给的提示这是给DP准备的题这道题N最大只有100边权范围是1到1000。这个数据范围很有讲究。如果是纯最短路N100根本不需要N这么小图论最短路算法处理上万点的图都没问题。但当你需要记录“每个点的所有可达时间集合”时100这个范围就合理了因为时间集合的大小会被限制在一个可控范围内。路径最多经过N-1条边每条边权最大1000所以一头牛从1到N的最晚到达时间不可能超过99乘1000也就是99000。这个数字恰好是一个可以接受的DP状态大小。换句话说题目的数据范围就是在暗示你请用与时间有关的动态规划而且这个时间上限可以安全地开成100000级别的数组或bitset。这也是我推荐大家在读题时多留一个心眼的地方数据范围不是白给的它往往在提示你算法的大方向。2. 核心思路让每个点记住“所有能到达的时刻集合”2.1 状态设计dp不是最短时间而是time-set既然只保留最短时间不够那我们就干脆把每个点的所有可能到达时间都存下来。具体来说对每个点u维护一个布尔数组或者bitsetdp[u]的第i位为1表示“存在一条从1到u的路径总用时正好是i”。初始状态很简单起点1在时刻0一定可达所以dp[1]的第0位设为1。其他点默认全0。对于一条有向边u - v边权为w如果u在时刻t可达那么从u出发经过这条边就能在时刻tw到达v。放到状态集合里相当于把dp[u]这个集合整体往后平移w秒再并到dp[v]里。写成集合语言就是dp[v] dp[v] ∪ (dp[u] w)你要是熟悉bitset这行代码简直就是为这道题量身定做的。如果不用bitset用bool数组也能做就是要把t从0到MAXT扫一遍能到达就更新dp[v][t w]为true。两种做法后面会详细对比。这里我认为最重要的思维转变是过去我们做最短路每个点只留一个数因为最短路满足最优子结构但这道题的时间同步性要求我们保留整个集合因为一次非最优的到达可能在终点成为“恰好同步”的关键。2.2 DAG与拓扑序先处理前驱再向后传递图是DAG所以存在拓扑序。为什么必须按拓扑序处理因为我们要保证处理到点u的时候所有能到达u的路径都已经把状态传过来了。如果随便按1到N的顺序扫可能会出现这种情况先处理了u的一条出边结果后面又发现另一条到u的路径导致u的状态更新了但这条新状态没来得及向后传递答案就错了。拓扑排序先把所有入度为0的点放进队列然后弹出队首u把u放进order数组接着把u的所有出边终点的入度减1如果某个终点的入度变成0就再把它入队。最终order数组就是合法的处理顺序。实际写的时候有个容易忽略的小问题要先把所有入度统计好再拓扑排序。输入时每次读入a到b的边就执行indeg[b]。这里的重边也不需要特殊处理每条边都累加入度DP时每条边也都会独立贡献状态不会冲突。2.3 用bitset加速“把一个集合整体加边权”如果纯粹用bool数组转移大概长这样for (int t 0; t MAXT; t) { if (dp[u][t]) { dp[v][t w] true; } }这个写法的正确性没有问题但复杂度是O(M乘MAXT)。M如果到10000MAXT如果到100000那就是十亿级别的操作虽然很多OJ数据比较温和但心里总是不踏实。用bitset可以直接把内层循环省掉。一个bitset100005里每一位就是一个时间点dp[u] w这一步相当于把整个集合的所有1一次性平移到高w的位置上然后再和dp[v]做按位或。一次移位加一次或运算底层按机器字处理100005位差不多只要1564个64位字就能搞定。整个程序最坏情况也就千万级别的字操作非常稳。这也是我想强调的一点信奥里bitset不只是用来做状态压缩的它很适合处理这种“状态集合整体平移”的DP。学会用bitset很多看似复杂度吃紧的时间集合题都能瞬间降一个量级。2.4 时间上界估算99条边乘1000状态集合的大小不能随便拍脑袋。开太大浪费内存开太小反复WA。对于P3116需要先推导一下最坏情况。DAG中一条路径不可能重复经过同一个点否则就成环了。所以从1到N的任意路径最多经过100个点也就是最多99条边。每条边的时间上限是1000。因此一头牛到达N的最晚可能时间是99乘1000等于99000。我们开数组的时候只要保证下标能到99000以上即可。我会习惯性开成100005留一点余量防止哪里边界条件没算准。有人为了省内存开10000那必挂因为合法的答案可能就是99000。另外要说明一点因为两头牛要同时到达我们最后要找的是两个bitset的交集也就是从0开始扫找到第一个时间t使Bessie的dp[N]第t位为1同时Elsie的dp[N]第t位也为1。早到的牛可以等待所以只要存在某个共同时间它们就可以在那个时间点碰头取最小的共同t作为答案即可。3. C实现从建图到AC的完整代码3.1 建图与拓扑排序实现建图时我把两条时间都塞进同一个结构体里这样边结构就统一了。每条边存终点to、Bessie用时t1、Elsie用时t2。vector邻接表足够不需要链式前向星。拓扑排序之前要先算indeg数组然后跑队列。这里有个实操经验如果输入数据里出现了环队列长度会小于Norder数组填不满。题目保证是DAG一般不会出现但调试时可以加一个判断如果cnt不等于N就说明数据非法或者你读入读错了。竞赛里加一行防御性判断不亏能帮你快速定位是自己建图错了还是数据有问题。3.2 两路DP同时向后推拓扑排序完成后按order数组顺序处理每个点。每个点u处理完就把它所有出边的终点v的bitset更新掉。注意这里是用两个独立的bitset数组一个记Bessie的所有可达时间一个记Elsie的所有可达时间。为什么可以把两个DP放在同一个拓扑循环里因为两张图共用同一套点和边只是边权不同。处理方式完全一样都是先处理完前驱再向后推。放在一起写代码更简洁也不会互相干扰。一个容易搞错的小地方是bitset左移方向。有人会写成dp[v] | dp[u] w那是倒着走了时间会往回退结果全是错的。这里必须想清楚从时刻t出发经过用时w的边到达时刻tw是往后加时间所以一定是左移w位。3.3 完整参考代码下面这份代码我在洛谷和USACO原题数据上都跑过可以直接当作模板参考。注释我尽量写得细一点。#include bits/stdc.h using namespace std; const int MAXN 105; const int MAXT 100005; struct Edge { int to; int t1, t2; }; int n, m; vectorEdge g[MAXN]; int indeg[MAXN]; int order[MAXN], cnt; // 两个独立的 bitset分别表示 Bessie 和 Elsie 在每个点的可达时间集合 bitsetMAXT bessie[MAXN]; bitsetMAXT elsie[MAXN]; void toposort() { queueint q; for (int i 1; i n; i) { if (indeg[i] 0) q.push(i); } while (!q.empty()) { int u q.front(); q.pop(); order[cnt] u; for (auto e : g[u]) { indeg[e.to]--; if (indeg[e.to] 0) q.push(e.to); } } } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin n m; for (int i 0; i m; i) { int a, b, c, d; cin a b c d; g[a].push_back({b, c, d}); indeg[b]; } toposort(); // 起点在时刻 0 可达 bessie[1][0] 1; elsie[1][0] 1; // 按拓扑序做集合 DP for (int i 0; i cnt; i) { int u order[i]; for (auto e : g[u]) { // 所有可达时刻整体 t1 bessie[e.to] | (bessie[u] e.t1); // 所有可达时刻整体 t2 elsie[e.to] | (elsie[u] e.t2); } } // 找两个时间集合的第一个公共时间 for (int t 0; t MAXT; t) { if (bessie[n][t] elsie[n][t]) { cout t \n; return 0; } } cout IMPOSSIBLE\n; return 0; }说几个代码层面的细节。bitset数组我放在全局区因为bitset100005的数组大约2.6MB左右放到main函数里面在部分OJ的栈限制下可能出问题全局变量就完全没这个顾虑。另外读入部分用了ios::sync_with_stdio(false)和cin.tie(nullptr)C的cin在刷题时一定要开这个不然大数据输入可能卡时间。3.4 bitset版本和普通bool数组版本的区别有些同学对bitset不熟我简单对比一下。bool数组版本相当于bool dp[MAXN][MAXT]; for (int i 0; i cnt; i) { int u order[i]; for (auto e : g[u]) { for (int t 0; t e.t1 MAXT; t) { if (dp[u][t]) dp[e.to][t e.t1] true; } } }这个写法的优点是容易理解不需要会bitset的位运算。缺点是内层还要扫一遍时间M稍大就慢。bitset版本的好处在于把“内层扫时间”这个循环用位运算替代了代码更短速度更快。我建议信奥选手都花点时间把bitset的常见操作练熟像、、|、、test()、.set()、.count()这些在后续很多集合类DP里都用得上。不过如果你的编译器环境比较老记得确认C版本支持bitset的流操作。最稳妥的做法就是用dp[v] | (dp[u] w)这种标准表达式几乎所有C11以上的环境都能直接编译通过。4. 易错点与调试实录4.1 容易忽略的N1边界情况题目没有说N一定大于1。如果N1那么起点就是终点两头牛已经在同一个地方最早碰头时间显然是0。上面代码里bessie[1][0]和elsie[1][0]都设为1最后扫描到t0时直接输出0逻辑正确。但很多人在写的时候会默认N至少是2或者把初始状态放到起点时没有考虑终点就是起点的情况最后输出IMPOSSIBLE。这种边界条件在比赛里非常坑一个小数据点就可能决定你AC还是WA。调试小技巧构造N1M0的数据如果程序不能输出0问题就出在初始化或者扫描起点上。4.2 MAXT开小了导致查不到答案我自己第一次提交就栽在这里。当时以为时间最多一万多开了15000结果有个点的路径很长合法答案远超这个值bitset左移时把高位信息全部丢掉了最后程序输出IMPOSSIBLE但实际明明有解。排查这类问题的方法很简单如果你怀疑答案是某个时间T可以在程序里把Bessie和Elsie到达N的所有时间都打印出来看看它们的最大值是否接近MAXT。如果最大值已经顶到MAXT-1那不是题目无解而是你数组开小了。MAXT直接按100005开稳。就算你懒得算99乘1000开100005也是安全的。要是你看到某些题解开500005理论上没问题内存也就多几MB但没必要。4.3 用拓扑序处理还是写成普通for循环这是另一个高频WA点。有人图省事不写拓扑排序直接写for (int u 1; u n; u) { for (auto e : g[u]) { bessie[e.to] | (bessie[u] e.t1); elsie[e.to] | (elsie[u] e.t2); } }如果点的编号恰好满足每条边都是从小编号指向大编号这个写法碰巧能过但一旦存在“1-3、2-3、1-2”这种跨层边按编号从1到N处理就可能漏状态。比如1-3先处理然后1-2和2-3后处理3被2更新的时间就没机会再往后传了。拓扑排序本质上就是把处理顺序固定成“前驱必然在前”只要按这个顺序跑一遍每个点的状态在被处理时一定是完整的。多写一个队列而已别在这个地方省事。4.4 输出格式和IMPOSSIBLE的大小写原题要求无解时输出大写的“IMPOSSIBLE”不是“Impossible”也不是“impossible”更不是“-1”。很多同学算法没问题却因为输出格式丢分非常可惜。我的习惯是把输出相关的字符串提前复制粘贴到代码里而不是手敲减少手误概率。另外要注意换行。按USACO等OJ的习惯每个输出末尾都要有换行符。cout IMPOSSIBLE\n;就够了。4.5 常见问题速查表问题现象可能原因解决办法答案偏小只保存每个点的最短到达时间丢掉了其他同步可能改成保存“所有可达时间集合”输出IMPOSSIBLE但实际有解MAXT开太小高位时间被bitset左移丢弃把MAXT开到100005或更大部分数据WA和AC反复没有按拓扑序转移后到前驱的状态没传下去先跑拓扑排序按order顺序DP程序崩溃或占内存超标bitset数组开在栈上把大数组定义成全局变量输出格式错误IMPOSSIBLE大小写或换行不对对照题面严格复制输出字符串N1时答案错误没有考虑起点就是终点保证dp[1][0]1扫描从t0开始4.6 我实测下来的几个调试技巧如果你在OJ上提交后WA但本地样例过了我建议你先自己造几个小数据把每个点的bitset内容输出出来。输出bitset可以直接用cout bessie[u]它会打印一串01。看到第几位是1就能判断转移方向对不对也能看到是不是有某个点一直没有被更新。还有一次我被重边坑过。题目并没有说两点之间只能有一条边如果存在多条相同起终点但时间不同的边我的邻接表写法天然支持但如果有人用二维数组存边权只存最后一次输入的值重边就把前面的覆盖了。所以用vector存边比用二维数组稳。最后再说一个通用经验这道题做完之后我对“时间集合DP”这类题的理解加深了很多。以后再碰到“求两条路径时间相等”或“求到达时间取模”之类的题目第一反应就应该是bitset存时间集合而不是执着于最短路。很多看起来像是图论的题内核其实是DP关键就看状态里需不需要保留多个可能性。我个人在实际操作中的体会是刷这种USACO老题AC本身不是最重要的重要的是把卡壳的那个点彻底想明白。P3116的卡点几乎都集中在“为什么不能只存最短时间”和“拓扑序为什么不能省”这两个问题上。想通之后代码二十分钟就能写完剩下的全是细节校验。如果你现在也被这题卡住不要急着看题解先按这个思路自己写一遍再回来对照上面的坑收获会大很多。