双重检验锁 html optimization video plot cmake stream vue动态绑定class vue标签 vue的优点 jquery拼接字符串 python正则匹配中文 mysql学习 python线程 如何配置python环境 python的编译器 python返回函数 java正则 安装java环境 java继承关键字 java环境部署 java成员变量 java获取url linux系统安装教程图解 hadoop权威指南 电脑必备软件排行榜 微信摇骰子表情包 vbs表白代码 生存猎人属性 视频加字幕软件 用流量打电话的软件 高通cpu排行 骰子动态图 什么模拟器最好 ppt格式刷怎么用 mathcad sqlprompt 内存条有什么用 主播音效 手机电池容量怎么看
当前位置: 首页 > 学习教程  > 编程语言

试题 历届试题 危险系数

2020/10/8 20:32:42 文章标签:

题目 问题描述 抗日战争时期,冀中平原的地道战曾发挥重要作用。地道的多个站点间有通道连接,形成了庞大的网络。但也有隐患,当敌人发现了某个站点后,其它站点间可能因此会失去联系。我们来定义一个危险系数DF(x,y):对于…

题目
问题描述
抗日战争时期,冀中平原的地道战曾发挥重要作用。地道的多个站点间有通道连接,形成了庞大的网络。但也有隐患,当敌人发现了某个站点后,其它站点间可能因此会失去联系。我们来定义一个危险系数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 <= n; u != v)代表一条通道;
最后1行,两个数u,v,代表询问两点之间的危险系数DF(u, v)。
输出格式一个整数,如果询问的两点不连通则输出-1.

思路:感觉开始题意都没搞太懂,弄了时间比较长,先构造一个图,然后对该图进行dfs,找到每个点到达目标点的次数,和路的总数量,只要两者相等就符合要求

代码:

import java.io.*;
import java.math.BigInteger;
import java.util.*;
public class 练习  {
 static Scanner sc=new Scanner(System.in);
 static int start,end,m,n,way,ans;
 static int [][]maps;//构图
 static int []a;//记录点
 static int []arr;
 public static void main(String[] args) {
  m=sc.nextInt();//记录点的个数
  n=sc.nextInt();//记录边的个数
  maps=new int[m+1][m+1];
  a=new int [m+1];
  arr=new int [m+1];
  for(int i=0;i<n;i++) {
   int v=sc.nextInt();
   int w=sc.nextInt();
   maps[v][w]=maps[w][v]=1;//存点构图
  }
  start=sc.nextInt();
  end=sc.nextInt();
  a[start]=1;
  dfs(start);
  for(int i=1;i<=m;i++) {
   if(i!=start&&i!=end) {
    if(arr[i]==way) {
     ans++;
    }
   }
  }
  System.out.println(ans);
 }
 private static int dfs(int tt) {
  int num=0;
  for(int i=1;i<=m;i++) {
   if(a[i]==0&&maps[tt][i]==1) {
    a[i]=1;
    if(i==end) {
     num++;
     way++;
     a[i]=0;
    }else {
     num+=dfs(i);
     a[i]=0;
    }
   }
  }
  arr[tt]+=num;
  return num;
 }
}

本文链接: http://www.dtmao.cc/news_show_250347.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?