来源P8604 [蓝桥杯 2013 国 C] 危险系数 - 洛谷目录题目背景题目描述输入格式输出格式输入输出样例 #1输入 #1输出 #1分析代码运行题目背景抗日战争时期冀中平原的地道战曾发挥重要作用。题目描述地道的多个站点间有通道连接形成了庞大的网络。但也有隐患当敌人发现了某个站点后其它站点间可能因此会失去联系。我们来定义一个危险系数 DF(x, y)对于两个站点 x 和 y(x 不等于 y)如果能找到一个站点 z当 z 被敌人破坏后x 和 y 不连通那么我们称 z 为关于 xy 的关键点。相应的对于任意一对站点 x 和 y危险系数 DF(x, y) 就表示为这两点之间的关键点个数。本题的任务是已知网络结构求两站点之间的危险系数。输入格式输入数据第一行包含 2 个整数 n(2 n 1000)m(0 m 2000)分别代表站点数通道数。接下来 m 行每行两个整数 uv(1 uv nu 不等于 v) 代表一条通道。最后 1 行两个数 uv代表询问两点之间的危险系数 DF(u, v)。输出格式一个整数如果询问的两点不连通则输出-1。输入输出样例 #1输入 #17 61 32 33 43 54 55 61 6输出 #12分析求危险系数就是在求两点间的关键点数量破坏了关键点两点就无法连通。因此先判断原图中起点和终点是否连通如果本来就不连通就直接输出 -1否则我们枚举每一个除了起点和终点之外的节点假设这个节点被破坏删除将它视作不可访问的点然后从起点做一次DFS深度优先搜索遍历图判断终点是否还能到达。如果终点不可达则说明当前被删除的节点是关键点危险系数加一。整个过程本质上是枚举每个节点并在模拟删除的图上做连通性判断。本道题用到了一个存图小技巧vector容器模拟邻接表存图vectorint e[1005]; // e[i]代表和i邻接的点e[u][i]就是u的邻接点表示u的第i个邻接点比如现在有6条边1-32-33-43-54-55-6存图结束后邻接表变为e[1] {3} e[2] {3} e[3] {1, 2, 4, 5}e[4] {3, 5} e[5] {3, 4, 6} e[6] {5}代码#include iostream #include vector #include cstring using namespace std; int n; // 站点数 int m; // 通道数 int u, v; // 要询问的两个点 vectorint e[1000005]; // 邻接表存图e[i]代表和i邻接的点 int v_pohuai; // 当前被破坏的点因为图的点大于1所以初始化可为0 int flag[1005]; // 访问标记 int ans; // 危险系数关键点数量 void DFS(int u); int main(){ cin n m; int temp_a 0, temp_b 0; // 相连的两个点 for(int i 1; i m; i){ cin temp_a temp_b; e[temp_a].push_back(temp_b); e[temp_b].push_back(temp_a); } cin u v; // 先判断原图是否连通不连通就直接输出-1 DFS(u); // 此时没有点被破坏可以自由搜索图中的点 if(!flag[v]){ cout -1; return 0; } // 枚举每一个点分别假设作为被破坏的点看看破坏后u能不能到v // x不等于y不等于z将除起点和终点的所有点一个一个设为被破坏的点 for(int i 1; i n; i){ // 如果当前点是起点或者终点就跳过 if(i u || i v){ continue; } // 重置访问数组 memset(flag, 0, sizeof(flag)); // 假设点i被破坏 v_pohuai i; // 以u作为起点做一次DFS但不能经过i判断破坏i之后还能不能到达v DFS(u); // 如果此时v不可达说明此时i是关键点 if(!flag[v]){ ans; } } cout ans; return 0; } // 深度优先搜索 // 从u出发遍历所有能到达的点 // 每次DFS结束后如果flag[i] 1说明u可以到达i void DFS(int u){ flag[u] 1; // 标记u已被访问 // 遍历u的所有邻接点 for(int i 0; i e[u].size(); i){ int j e[u][i]; // u的邻接点e[u][i]的含义是u的第i个邻接点 // 如果这个邻接点不是被删除的点并且还没有被访问过就从这个点开始搜索整个图 if(j ! v_pohuai !flag[j]){ DFS(j); // 深搜 } } }运行
《算法集训》第7题--危险系数
来源P8604 [蓝桥杯 2013 国 C] 危险系数 - 洛谷目录题目背景题目描述输入格式输出格式输入输出样例 #1输入 #1输出 #1分析代码运行题目背景抗日战争时期冀中平原的地道战曾发挥重要作用。题目描述地道的多个站点间有通道连接形成了庞大的网络。但也有隐患当敌人发现了某个站点后其它站点间可能因此会失去联系。我们来定义一个危险系数 DF(x, y)对于两个站点 x 和 y(x 不等于 y)如果能找到一个站点 z当 z 被敌人破坏后x 和 y 不连通那么我们称 z 为关于 xy 的关键点。相应的对于任意一对站点 x 和 y危险系数 DF(x, y) 就表示为这两点之间的关键点个数。本题的任务是已知网络结构求两站点之间的危险系数。输入格式输入数据第一行包含 2 个整数 n(2 n 1000)m(0 m 2000)分别代表站点数通道数。接下来 m 行每行两个整数 uv(1 uv nu 不等于 v) 代表一条通道。最后 1 行两个数 uv代表询问两点之间的危险系数 DF(u, v)。输出格式一个整数如果询问的两点不连通则输出-1。输入输出样例 #1输入 #17 61 32 33 43 54 55 61 6输出 #12分析求危险系数就是在求两点间的关键点数量破坏了关键点两点就无法连通。因此先判断原图中起点和终点是否连通如果本来就不连通就直接输出 -1否则我们枚举每一个除了起点和终点之外的节点假设这个节点被破坏删除将它视作不可访问的点然后从起点做一次DFS深度优先搜索遍历图判断终点是否还能到达。如果终点不可达则说明当前被删除的节点是关键点危险系数加一。整个过程本质上是枚举每个节点并在模拟删除的图上做连通性判断。本道题用到了一个存图小技巧vector容器模拟邻接表存图vectorint e[1005]; // e[i]代表和i邻接的点e[u][i]就是u的邻接点表示u的第i个邻接点比如现在有6条边1-32-33-43-54-55-6存图结束后邻接表变为e[1] {3} e[2] {3} e[3] {1, 2, 4, 5}e[4] {3, 5} e[5] {3, 4, 6} e[6] {5}代码#include iostream #include vector #include cstring using namespace std; int n; // 站点数 int m; // 通道数 int u, v; // 要询问的两个点 vectorint e[1000005]; // 邻接表存图e[i]代表和i邻接的点 int v_pohuai; // 当前被破坏的点因为图的点大于1所以初始化可为0 int flag[1005]; // 访问标记 int ans; // 危险系数关键点数量 void DFS(int u); int main(){ cin n m; int temp_a 0, temp_b 0; // 相连的两个点 for(int i 1; i m; i){ cin temp_a temp_b; e[temp_a].push_back(temp_b); e[temp_b].push_back(temp_a); } cin u v; // 先判断原图是否连通不连通就直接输出-1 DFS(u); // 此时没有点被破坏可以自由搜索图中的点 if(!flag[v]){ cout -1; return 0; } // 枚举每一个点分别假设作为被破坏的点看看破坏后u能不能到v // x不等于y不等于z将除起点和终点的所有点一个一个设为被破坏的点 for(int i 1; i n; i){ // 如果当前点是起点或者终点就跳过 if(i u || i v){ continue; } // 重置访问数组 memset(flag, 0, sizeof(flag)); // 假设点i被破坏 v_pohuai i; // 以u作为起点做一次DFS但不能经过i判断破坏i之后还能不能到达v DFS(u); // 如果此时v不可达说明此时i是关键点 if(!flag[v]){ ans; } } cout ans; return 0; } // 深度优先搜索 // 从u出发遍历所有能到达的点 // 每次DFS结束后如果flag[i] 1说明u可以到达i void DFS(int u){ flag[u] 1; // 标记u已被访问 // 遍历u的所有邻接点 for(int i 0; i e[u].size(); i){ int j e[u][i]; // u的邻接点e[u][i]的含义是u的第i个邻接点 // 如果这个邻接点不是被删除的点并且还没有被访问过就从这个点开始搜索整个图 if(j ! v_pohuai !flag[j]){ DFS(j); // 深搜 } } }运行
