星际旅行

问题描述

小明国庆节准备去某星系进行星际旅行，这个星系里一共有 nn 个星球，其中布置了 mm 道双向传送门，第 ii 道传送门可以连接 ai,bi*ai,bi 两颗星球（ai≠biai\=bi* 且任意两颗星球之间最多只有一个传送门）。

他看中了一款 “旅游盲盒”，一共有 QQ 个盲盒，第 ii 个盲盒里的旅行方案规定了旅行的起始星球 xi*xi 和最多可以使用传送门的次数 yiyi*。只要从起始星球出发，使用传送门不超过规定次数能到达的所有星球都可以去旅行。

小明关心在每个方案中有多少个星球可以旅行到。小明只能在这些盲盒里随机选一个购买，他想知道能旅行到的不同星球的数量的期望是多少。

输入格式

输入共 m+Q+1m+Q+1 行。

第一行为三个正整数 n,m,Qn,m,Q 。

后面 mm 行，每行两个正整数 ai,bi*ai,bi* 。

后面 QQ 行，每行两个整数 xi,yi*xi,yi* 。

输出格式

输出共一行，一个浮点数（四舍五入保留两位小数）。

样例输入

3 2 3
1 2
2 3
2 1
2 0
1 1

样例输出

2.00

样例说明

第一个盲盒可以旅行到 1,2,31,2,3。

第二个盲盒可以旅行到 22。

第三个盲盒可以旅行到 1,21,2。

所以期望是 (3+1+2)/3=2.00(3+1+2)/3=2.00。

解决

import java.util.*;
// 1:无需package
// 2: 类名必须Main, 不可修改

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 ) 表示一个对称邻接矩阵。

例如，题目描述中的两个牧场的矩阵描述如下：

  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

输入样例：

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

输出样例：

22.071068

解决

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));
    }
}