![P1700 [USACO19OPEN] Milk Factory B](http://pic.xiahunao.cn/yaotu/P1700 [USACO19OPEN] Milk Factory B)
记录137#includebits/stdc.h using namespace std; const int N105;// 定义常量N表示加工站数量的最大范围题目保证N100 vectorint g[N];// 定义邻接表gg[u]存储从结点u出发能直接到达的所有结点 bool vis[N];// 定义访问标记数组用于DFS时防止重复访问 bool found_target0; // 定义标志变量用于在DFS中记录是否成功找到了目标点target // 深度优先搜索DFS函数从当前结点u出发寻找目标点target void dfs(int u,int target){ if(found_target) return; // 如果之前已经找到了目标点直接剪枝返回 if(utarget){ // 如果当前结点u就是目标点target found_target1; // 标记已找到目标点 return; // 直接返回 } vis[u]1; // 标记当前结点u已被访问过 for(int v:g[u]){ // 遍历当前结点u能到达的所有相邻结点v if(!vis[v]) dfs(v,target); }// 如果结点v还没有被访问过继续从v出发进行深搜 } int main(){ ios::sync_with_stdio(false); cin.tie(0); int n;// 定义变量n表示加工站的数量 cinn; // 读入加工站数量n int a,b; // 定义变量a和b用来临时存储每条传送带的起点和终点 for(int i1;in;i){ //n-1条边 cinab; // 读入一条从a指向b的传送带 g[a].push_back(b); // 将b加入a的邻接表表示a能走到b } // 从小到大枚举每一个结点i作为终点 for(int i1;in;i){ bool is_ok1; // 假设当前目标是合法的 // 检查所有其他结点j看是否都能通过DFS走到目标i for(int j1;jn;j){ if(ji) continue; // 如果j就是目标本身不需要检查 memset(vis,0,sizeof(vis)); //走之前重置访问数组 found_target0; // 一开始没找到目标 dfs(j,i); // 从结点j出发尝试寻找目标i if(!found_target){ // 如果从j出发无法走到目标i is_ok0; // 当前目标不合法 break; //提前跳出内层循环检查下一个target } } if(is_ok){ // 如果当前i满足所有结点都能到达它 couti\n; // 输出最小的满足条件的i return 0; // 程序直接结束 } } cout-1; // 如果遍历完所有target都不合法输出-1 return 0;//程序正常结束 }题目传送门https://www.luogu.com.cn/problem/P1700前言我是一名专注信奥赛CSP-J/S、NOIP的教练。如果你觉得这篇题解对你有帮助欢迎点击关注我的CSDN账号我会持续更新高质量算法解析。我深知算法思维的构建远比单纯通过题目更重要本系列题解不局限于AC代码的堆砌而是致力于拆解题目背后的逻辑链条与核心知识点备赛路上若遇瓶颈欢迎随时评论或私信我将甄选典型疑难问题通过视频讲解或撰写专项文章的形式为你提供深度答疑。核心解题思路这道题是一道典型的图论与暴力枚举结合的问题。问题转化题目给出了一个包含 NN 个结点和 N−1N−1 条有向边的图本质是一棵有向树。我们需要找到一个结点 ii 使得图中所有其他结点都能通过有向边到达 ii 。如果存在多个这样的结点输出编号最小的那个如果不存在输出 -1。算法设计暴力枚举 DFS由于题目中 NN 的最大值仅为 100数据规模非常小。我们可以采用最直观的暴力枚举法依次假设每一个结点 ii 从 1 到 NN 是我们要找的“终点”。对于每一个假设的终点 ii 我们从图中的每一个其他结点 jj 出发使用深度优先搜索DFS或广度优先搜索BFS判断是否能沿着有向边到达 ii 。如果所有结点 jj 都能到达 ii 那么 ii 就是合法的答案。因为我们是从 1 开始从小到大枚举的所以找到的第一个合法 ii 必然是最小的。代码分块详细解释1. 头文件、常量与全局变量定义#includebits/stdc.h using namespace std; const int N105; // 定义常量 N表示加工站数量的最大范围题目保证 N100 vectorint g[N]; // 定义邻接表 gg[u] 存储从结点 u 出发能直接到达的所有结点 bool vis[N]; // 定义访问标记数组用于 DFS 时防止重复访问 bool found_target0; // 定义标志变量用于在 DFS 中记录是否成功找到了目标点 target详细分析这部分搭建了图论算法的基础。由于是有向图我们使用vectorint g[N]来构建邻接表g[a].push_back(b)表示存在一条从 aa 指向 bb 的单向传送带。vis数组是 DFS 的标配防止在图中走环路导致死循环。found_target是一个全局剪枝变量一旦在某次 DFS 中找到了目标就立刻停止后续的搜索提高效率。2. 深度优先搜索DFS函数// 深度优先搜索DFS函数从当前结点 u 出发寻找目标点 target void dfs(int u, int target){ if(found_target) return; // 如果之前已经找到了目标点直接剪枝返回 if(u target){ // 如果当前结点 u 就是目标点 target found_target 1; // 标记已找到目标点 return; // 直接返回 } vis[u] 1; // 标记当前结点 u 已被访问过 for(int v : g[u]){ // 遍历当前结点 u 能到达的所有相邻结点 v if(!vis[v]) dfs(v, target); } // 如果结点 v 还没有被访问过继续从 v 出发进行深搜 }详细分析这是判断“点 jj 能否到达点 ii ”的核心工具。剪枝优化函数开头首先检查found_target如果之前的搜索路径已经找到了目标当前递归分支就没有继续的必要了直接返回。命中目标如果当前遍历到的结点u等于目标target说明路径打通将全局标志置为 1 并返回。递归扩展如果没有找到目标就标记当前点已访问然后遍历它的所有出边。只有当相邻结点v未被访问时才递归进入这保证了搜索的有限性。3. 主函数建图与输入处理int main(){ ios::sync_with_stdio(false); cin.tie(0); int n; // 定义变量 n表示加工站的数量 cin n; // 读入加工站数量 n int a, b; // 定义变量 a 和 b用来临时存储每条传送带的起点和终点 for(int i 1; i n; i){ // n-1 条边 cin a b; // 读入一条从 a 指向 b 的传送带 g[a].push_back(b); // 将 b 加入 a 的邻接表表示 a 能走到 b }详细分析标准的 IO 加速和建图过程。题目给出了 N−1N−1 条有向边我们按照输入顺序将每条边的终点加入起点的邻接表中从而构建出完整的有向图。4. 核心逻辑枚举终点与合法性检查// 从小到大枚举每一个结点 i 作为终点 for(int i 1; i n; i){ bool is_ok 1; // 假设当前目标是合法的 // 检查所有其他结点 j看是否都能通过 DFS 走到目标 i for(int j 1; j n; j){ if(j i) continue; // 如果 j 就是目标本身不需要检查 memset(vis, 0, sizeof(vis)); // 走之前重置访问数组 found_target 0; // 一开始没找到目标 dfs(j, i); // 从结点 j 出发尝试寻找目标 i if(!found_target){ // 如果从 j 出发无法走到目标 i is_ok 0; // 当前目标不合法 break; // 提前跳出内层循环检查下一个 target } } if(is_ok){ // 如果当前 i 满足所有结点都能到达它 cout i \n; // 输出最小的满足条件的 i return 0; // 程序直接结束 } } cout -1; // 如果遍历完所有 target 都不合法输出 -1 return 0; // 程序正常结束 }详细分析这是算法的主体部分采用了双重循环。外层循环枚举假设我们依次假设结点 ii 是那个“所有点都能到达的终点”。因为题目要求输出最小的 ii 所以我们从 1 开始从小到大枚举一旦找到合法的就可以直接输出并结束程序。内层循环验证假设对于当前的假设终点 ii 我们需要验证图中的每一个其他结点 jj 是否都能到达它。状态重置每次从一个新的起点 jj 开始 DFS 之前必须将访问数组vis清零并将found_target重置为 0。这是因为每次 DFS 都是一次全新的探索。提前终止如果在验证过程中发现有任何一个结点 jj 无法到达 ii 即!found_target那么当前的 ii 肯定不是答案直接break跳出内层循环去测试下一个 ii 。这极大地减少了不必要的计算。核心逻辑总结表代码模块核心变量/操作精炼作用解决的痛点数据结构vectorint g[N]使用邻接表存储有向图高效存储单向传送带方便通过起点快速找到所有能直接到达的终点路径搜索dfs(u, target)判断从 u 到 target 是否有通路解决有向图中两点连通性的判断问题防死循环vis[u]1与if(!vis[v])记录已访问的结点防止在 DFS 过程中因为图中存在环路或重复路径而导致无限递归全局剪枝found_target记录目标是否已被找到一旦在 DFS 的某条分支中找到了目标立即停止所有后续搜索提升效率暴力枚举双重for循环依次假设每个点为终点并验证利用 N≤100N≤100 的小数据范围用简单直观的暴力法替代复杂的图论算法
P1700 [USACO19OPEN] Milk Factory B
发布时间：2026/7/7 6:59:35
记录137#includebits/stdc.h using namespace std; const int N105;// 定义常量N表示加工站数量的最大范围题目保证N100 vectorint g[N];// 定义邻接表gg[u]存储从结点u出发能直接到达的所有结点 bool vis[N];// 定义访问标记数组用于DFS时防止重复访问 bool found_target0; // 定义标志变量用于在DFS中记录是否成功找到了目标点target // 深度优先搜索DFS函数从当前结点u出发寻找目标点target void dfs(int u,int target){ if(found_target) return; // 如果之前已经找到了目标点直接剪枝返回 if(utarget){ // 如果当前结点u就是目标点target found_target1; // 标记已找到目标点 return; // 直接返回 } vis[u]1; // 标记当前结点u已被访问过 for(int v:g[u]){ // 遍历当前结点u能到达的所有相邻结点v if(!vis[v]) dfs(v,target); }// 如果结点v还没有被访问过继续从v出发进行深搜 } int main(){ ios::sync_with_stdio(false); cin.tie(0); int n;// 定义变量n表示加工站的数量 cinn; // 读入加工站数量n int a,b; // 定义变量a和b用来临时存储每条传送带的起点和终点 for(int i1;in;i){ //n-1条边 cinab; // 读入一条从a指向b的传送带 g[a].push_back(b); // 将b加入a的邻接表表示a能走到b } // 从小到大枚举每一个结点i作为终点 for(int i1;in;i){ bool is_ok1; // 假设当前目标是合法的 // 检查所有其他结点j看是否都能通过DFS走到目标i for(int j1;jn;j){ if(ji) continue; // 如果j就是目标本身不需要检查 memset(vis,0,sizeof(vis)); //走之前重置访问数组 found_target0; // 一开始没找到目标 dfs(j,i); // 从结点j出发尝试寻找目标i if(!found_target){ // 如果从j出发无法走到目标i is_ok0; // 当前目标不合法 break; //提前跳出内层循环检查下一个target } } if(is_ok){ // 如果当前i满足所有结点都能到达它 couti\n; // 输出最小的满足条件的i return 0; // 程序直接结束 } } cout-1; // 如果遍历完所有target都不合法输出-1 return 0;//程序正常结束 }题目传送门https://www.luogu.com.cn/problem/P1700前言我是一名专注信奥赛CSP-J/S、NOIP的教练。如果你觉得这篇题解对你有帮助欢迎点击关注我的CSDN账号我会持续更新高质量算法解析。我深知算法思维的构建远比单纯通过题目更重要本系列题解不局限于AC代码的堆砌而是致力于拆解题目背后的逻辑链条与核心知识点备赛路上若遇瓶颈欢迎随时评论或私信我将甄选典型疑难问题通过视频讲解或撰写专项文章的形式为你提供深度答疑。核心解题思路这道题是一道典型的图论与暴力枚举结合的问题。问题转化题目给出了一个包含 NN 个结点和 N−1N−1 条有向边的图本质是一棵有向树。我们需要找到一个结点 ii 使得图中所有其他结点都能通过有向边到达 ii 。如果存在多个这样的结点输出编号最小的那个如果不存在输出 -1。算法设计暴力枚举 DFS由于题目中 NN 的最大值仅为 100数据规模非常小。我们可以采用最直观的暴力枚举法依次假设每一个结点 ii 从 1 到 NN 是我们要找的“终点”。对于每一个假设的终点 ii 我们从图中的每一个其他结点 jj 出发使用深度优先搜索DFS或广度优先搜索BFS判断是否能沿着有向边到达 ii 。如果所有结点 jj 都能到达 ii 那么 ii 就是合法的答案。因为我们是从 1 开始从小到大枚举的所以找到的第一个合法 ii 必然是最小的。代码分块详细解释1. 头文件、常量与全局变量定义#includebits/stdc.h using namespace std; const int N105; // 定义常量 N表示加工站数量的最大范围题目保证 N100 vectorint g[N]; // 定义邻接表 gg[u] 存储从结点 u 出发能直接到达的所有结点 bool vis[N]; // 定义访问标记数组用于 DFS 时防止重复访问 bool found_target0; // 定义标志变量用于在 DFS 中记录是否成功找到了目标点 target详细分析这部分搭建了图论算法的基础。由于是有向图我们使用vectorint g[N]来构建邻接表g[a].push_back(b)表示存在一条从 aa 指向 bb 的单向传送带。vis数组是 DFS 的标配防止在图中走环路导致死循环。found_target是一个全局剪枝变量一旦在某次 DFS 中找到了目标就立刻停止后续的搜索提高效率。2. 深度优先搜索DFS函数// 深度优先搜索DFS函数从当前结点 u 出发寻找目标点 target void dfs(int u, int target){ if(found_target) return; // 如果之前已经找到了目标点直接剪枝返回 if(u target){ // 如果当前结点 u 就是目标点 target found_target 1; // 标记已找到目标点 return; // 直接返回 } vis[u] 1; // 标记当前结点 u 已被访问过 for(int v : g[u]){ // 遍历当前结点 u 能到达的所有相邻结点 v if(!vis[v]) dfs(v, target); } // 如果结点 v 还没有被访问过继续从 v 出发进行深搜 }详细分析这是判断“点 jj 能否到达点 ii ”的核心工具。剪枝优化函数开头首先检查found_target如果之前的搜索路径已经找到了目标当前递归分支就没有继续的必要了直接返回。命中目标如果当前遍历到的结点u等于目标target说明路径打通将全局标志置为 1 并返回。递归扩展如果没有找到目标就标记当前点已访问然后遍历它的所有出边。只有当相邻结点v未被访问时才递归进入这保证了搜索的有限性。3. 主函数建图与输入处理int main(){ ios::sync_with_stdio(false); cin.tie(0); int n; // 定义变量 n表示加工站的数量 cin n; // 读入加工站数量 n int a, b; // 定义变量 a 和 b用来临时存储每条传送带的起点和终点 for(int i 1; i n; i){ // n-1 条边 cin a b; // 读入一条从 a 指向 b 的传送带 g[a].push_back(b); // 将 b 加入 a 的邻接表表示 a 能走到 b }详细分析标准的 IO 加速和建图过程。题目给出了 N−1N−1 条有向边我们按照输入顺序将每条边的终点加入起点的邻接表中从而构建出完整的有向图。4. 核心逻辑枚举终点与合法性检查// 从小到大枚举每一个结点 i 作为终点 for(int i 1; i n; i){ bool is_ok 1; // 假设当前目标是合法的 // 检查所有其他结点 j看是否都能通过 DFS 走到目标 i for(int j 1; j n; j){ if(j i) continue; // 如果 j 就是目标本身不需要检查 memset(vis, 0, sizeof(vis)); // 走之前重置访问数组 found_target 0; // 一开始没找到目标 dfs(j, i); // 从结点 j 出发尝试寻找目标 i if(!found_target){ // 如果从 j 出发无法走到目标 i is_ok 0; // 当前目标不合法 break; // 提前跳出内层循环检查下一个 target } } if(is_ok){ // 如果当前 i 满足所有结点都能到达它 cout i \n; // 输出最小的满足条件的 i return 0; // 程序直接结束 } } cout -1; // 如果遍历完所有 target 都不合法输出 -1 return 0; // 程序正常结束 }详细分析这是算法的主体部分采用了双重循环。外层循环枚举假设我们依次假设结点 ii 是那个“所有点都能到达的终点”。因为题目要求输出最小的 ii 所以我们从 1 开始从小到大枚举一旦找到合法的就可以直接输出并结束程序。内层循环验证假设对于当前的假设终点 ii 我们需要验证图中的每一个其他结点 jj 是否都能到达它。状态重置每次从一个新的起点 jj 开始 DFS 之前必须将访问数组vis清零并将found_target重置为 0。这是因为每次 DFS 都是一次全新的探索。提前终止如果在验证过程中发现有任何一个结点 jj 无法到达 ii 即!found_target那么当前的 ii 肯定不是答案直接break跳出内层循环去测试下一个 ii 。这极大地减少了不必要的计算。核心逻辑总结表代码模块核心变量/操作精炼作用解决的痛点数据结构vectorint g[N]使用邻接表存储有向图高效存储单向传送带方便通过起点快速找到所有能直接到达的终点路径搜索dfs(u, target)判断从 u 到 target 是否有通路解决有向图中两点连通性的判断问题防死循环vis[u]1与if(!vis[v])记录已访问的结点防止在 DFS 过程中因为图中存在环路或重复路径而导致无限递归全局剪枝found_target记录目标是否已被找到一旦在 DFS 的某条分支中找到了目标立即停止所有后续搜索提升效率暴力枚举双重for循环依次假设每个点为终点并验证利用 N≤100N≤100 的小数据范围用简单直观的暴力法替代复杂的图论算法
 组件封装全解)
 获取与实战)
