蓝桥杯 历届试题 危险系数

地道的多个站点间有通道连接，形成了庞大的网络。但也有隐患，当敌人发现了某个站点后，其它站点间可能因此会失去联系。 我们来定义一个危险系数DF(x,y)： 对于两个站点x和y (x != y), 如果能找到一个站点z，当z被敌人破坏后，x和y不连通，那么我们称z为关于x,y的关键点。相应的，对于任意一对站点x和y，危险系数DF(x,y)就表示为这两点之间的关键点个数。 本题的任务是：已知网络结构，求两站点之间的危险系数。 输入数据第一行包含2个整数n(2 = n = 1000), m(0 = m = 2000),分别代表站点数，通道数； 接下来m行，每行两个整数 u,v (1 = u, v u != v)代表一条通道； 最后1行，两个数u,v，代表询问两点之间的危险系数DF(u, v)。 一个整数，如果询问的两点不连通则输出-1. 2

//过不了，不知道错哪了.....

#include iostream 

#include cstring 

#include cstdio 

#include algorithm 

#include vector 

#define MAX 0x3f3f3f3f

#define N 1005 

using namespace std;

vector int g[1005];

int dfs_clock;

int pre[N], low[N], iscut[N];

void dfs(int u, int fa){//tarjan算法求出割点 

 low[u] = pre[u] = ++dfs_clock;

 int len = g[u].size();

 int child = 0;//记录和u节点连接的强连通分量的数目 

 for(int i=0; i ++i){

 int v = g[u][i];

 if(v!=fa pre[u] pre[v]){

 if(pre[v] == 0){

 ++child;

 dfs(v, u);

 low[u] = min(low[u], low[v]);

 } else 

 low[u] = min(low[u], pre[v]);

 if(low[v] = pre[u]) iscut[u] = 1;

 if(fa==-1 child==1) iscut[u] = 0;//如果是第一个搜索的节点（根节点），且和它连接的子数的个数为1，那么该节点不是割点 

int ans;

int uu, vv;//询问两点DF(uu,vv)的值 

bool search(int u){//搜索uu-- vv的这段路，如果uu，vv两点之间存在割点，那么个点一定存在搜索的这段路中 

 if(u == vv) return true;

 int len = g[u].size();

 for(int i=0; i ++i){

 int v = g[u][i];

 if(!pre[v]){

 pre[v] = 1;

 if(search(v)){

 if(u!=uu iscut[u]) ++ans;

 return true;

 return false;

int main(){

 int n, m;

 while(scanf("%d%d", n, m) != EOF){

 dfs_clock = 0; 

 memset(pre, 0, sizeof(pre));

 memset(low, 0, sizeof(low));

 memset(iscut, 0, sizeof(iscut));

 for(int i=1; i ++i) g[i].clear();

 while(m--){

 int u, v;

 cin u v;

 g[u].push_back(v);

 g[v].push_back(u);

 scanf("%d%d", uu, vv);

 for(int i=1; i ++i)

 if(!pre[i])

 dfs(i, -1);

 ans = 0;

 memset(pre, 0, sizeof(pre));

 pre[uu] = 1;

 if(!search(uu)) ans = -1;

 printf("%d\n", ans);

 return 0;

}

天梯赛二阶题——L2-015 互评成绩（25 分） 学生互评作业的简单规则是这样定的：每个人的作业会被k个同学评审，得到k个成绩。系统需要去掉一个最高分和一个最低分，将剩下的分数取平均，就得到这个学生的最后成绩。本题就要求你编写这个互评系统的算分模块。
试题 历届真题 四平方和【第七届】【省赛】【B组】 四平方和定理，又称为拉格朗日定理： 每个正整数都可以表示为至多4个正整数的平方和。 如果把0包括进去，就正好可以表示为4个数的平方和。
数学分析高等代数考研试题荟萃[更新至2017年12月15日] 需要请点击链接. 10001北京大学2016-2017-1高等代数I期末考试试题 10001北京大学87,96-14,17年数学分析考研试题 (05含解答) 10001北京大学96-02,05,07,08,10-14 年高等代数考研试题 10002中国人民大学99,0...