星际旅行
问题描述
小明国庆节准备去某星系进行星际旅行，这个星系里一共有 n_n_ 个星球，其中布置了 m_m_ 道双向传送门，第 i_i_ 道传送门可以连接 ai,bi*ai_,_bi 两颗星球（ai≠bi_a**i\=_b**i* 且任意两颗星球之间最多只有一个传送门）。
他看中了一款 “旅游盲盒”，一共有 Q_Q_ 个盲盒，第 i_i_ 个盲盒里的旅行方案规定了旅行的起始星球 xi*xi _和最多可以使用传送门的次数 yi_yi*。只要从起始星球出发，使用传送门不超过规定次数能到达的所有星球都可以去旅行。
小明关心在每个方案中有多少个星球可以旅行到。小明只能在这些盲盒里随机选一个购买，他想知道能旅行到的不同星球的数量的期望是多少。
输入格式
输入共 m+Q+1_m_+Q+1 行。
第一行为三个正整数 n,m,Q_n_,m,Q 。
后面 m_m_ 行，每行两个正整数 ai,bi*ai_,_bi* 。
后面 Q_Q_ 行，每行两个整数 xi,yi*xi_,_yi* 。
输出格式
输出共一行，一个浮点数（四舍五入保留两位小数）。
样例输入
1
2
3
4
5
6
| 3 2 3
1 2
2 3
2 1
2 0
1 1
|
样例输出
样例说明
第一个盲盒可以旅行到 1,2,31,2,3。
第二个盲盒可以旅行到 22。
第三个盲盒可以旅行到 1,21,2。
所以期望是 (3+1+2)/3=2.00(3+1+2)/3=2.00。
解决
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
| import java.util.*;
public class Main {
static int n,m,q;
static int[][]con;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n=sc.nextInt();
m=sc.nextInt();
q=sc.nextInt();
con=new int[n+1][n+1];
for(int i=1;i<=n;i++){
Arrays.fill(con[i],3010);
}
for(int i=1;i<=n;i++){
con[i][i]=0;
}
for(int i=0;i<m;i++){
int a=sc.nextInt();
int b=sc.nextInt();
con[a][b]=1;
con[b][a]=1;
}
for(int k=1;k<=n;k++){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
con[i][j]=Math.min(con[i][j],con[i][k]+con[k][j]);
}
}
}
int ans=0;
for(int i=0;i<q;i++){
int x=sc.nextInt();
int y=sc.nextInt();
int count=0;
for(int j=1;j<=n;j++){
if(con[x][j]<=y)count++;
}
ans+=count;
}
System.out.printf("%.2f",(double)ans/q);
}
}
|
牛的旅行
题目链接
牛的旅行
问题描述
农民John的农场里有很多牧区，有的路径连接一些特定的牧区。
一片所有连通的牧区称为一个牧场。
但是就目前而言，你能看到至少有两个牧区不连通。
现在，John想在农场里添加一条路径（注意，恰好一条）。
一个牧场的直径就是牧场中最远的两个牧区的距离（本题中所提到的所有距离指的都是最短的距离）。
考虑如下的两个牧场，每一个牧区都有自己的坐标：
图 1 是有 5 个牧区的牧场，牧区用“*”表示，路径用直线表示。
图 1 所示的牧场的直径大约是 12.07106, 最远的两个牧区是 A 和 E，它们之间的最短路径是 A-B-E。
图 2 是另一个牧场。
这两个牧场都在John的农场上。
John将会在两个牧场中各选一个牧区，然后用一条路径连起来，使得连通后这个新的更大的牧场有最小的直径。
注意，如果两条路径中途相交，我们不认为它们是连通的。
只有两条路径在同一个牧区相交，我们才认为它们是连通的。
现在请你编程找出一条连接两个不同牧场的路径，使得连上这条路径后，所有牧场（生成的新牧场和原有牧场）中直径最大的牧场的直径尽可能小。
输出这个直径最小可能值。
输入格式
第 1 行：一个整数 N, 表示牧区数；
第 2 到 N+1 行：每行两个整数 X,Y， 表示 N 个牧区的坐标。每个牧区的坐标都是不一样的。
第 N+2 行到第 2*N+1 行：每行包括 N 个数字 ( 0或1 ) 表示一个对称邻接矩阵。
例如，题目描述中的两个牧场的矩阵描述如下：
1
2
3
4
5
6
7
8
9
| A B C D E F G H
A 0 1 0 0 0 0 0 0
B 1 0 1 1 1 0 0 0
C 0 1 0 0 1 0 0 0
D 0 1 0 0 1 0 0 0
E 0 1 1 1 0 0 0 0
F 0 0 0 0 0 0 1 0
G 0 0 0 0 0 1 0 1
H 0 0 0 0 0 0 1 0
|
输入数据中至少包括两个不连通的牧区。
输出格式
只有一行，包括一个实数，表示所求答案。
数字保留六位小数。
数据范围
1≤N≤1501≤N≤150, 0≤X,Y≤1050≤X,Y≤105
输入样例：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| 8
10 10
15 10
20 10
15 15
20 15
30 15
25 10
30 10
01000000
10111000
01001000
01001000
01110000
00000010
00000101
00000010
|
输出样例：
解决
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
| import java.util.*;
class PII{
int x,y;
public PII(int x,int y){
this.x=x;
this.y=y;
}
}
public class Main{
static int N=155,INF=(int)1e20;
static int n;
static PII[]q=new PII[N];
static char[][]g=new char[N][N];
static double[][]dist=new double[N][N];
static double[]maxd=new double[N];
public static double get_dist(PII i,PII j){
int dx=i.x-j.x,dy=i.y-j.y;
return (double)Math.sqrt(dx*dx+dy*dy);
}
public static void floyd(){
for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++){
dist[i][j]=Math.min(dist[i][j],dist[i][k]+dist[k][j]);
}
}
public static void main(String[]args){
Scanner sc=new Scanner(System.in);
n=sc.nextInt();
for(int i=1;i<=n;i++){
int x=sc.nextInt();
int y=sc.nextInt();
q[i]=new PII(x,y);
}
for(int i=1;i<=n;i++){
String s=sc.next();
for(int j=1;j<=n;j++){
g[i][j]=s.charAt(j-1);
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(i!=j){
if(g[i][j]=='1')dist[i][j]=get_dist(q[i],q[j]);
else dist[i][j]=INF;
}
}
}
floyd();
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(dist[i][j]<INF)
maxd[i]=Math.max(maxd[i],dist[i][j]);
}
}
double res1=0;
for(int i=1;i<=n;i++)res1=Math.max(res1,maxd[i]);
double res2=INF;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(dist[i][j]>=INF){
res2=Math.min(res2,get_dist(q[i],q[j])+maxd[i]+maxd[j]);
}
}
}
System.out.printf("%.6f",Math.max(res1,res2));
}
}
|
