翻译
查看原帖
翻译
185864
BqtMtsZDnlpsT楼主2020/8/11 14:41
  • GraphlandGraphland,有许多城市,但没有公路。你要在 GraphlandGraphland 中同一个州内的城市之间修建道路,并将使用铁路将不同州之间的城市连接起来。为了将修建公路和铁路的成本降到最低,政府还希望只修建必要的公路和铁路,以便在全国任何一对城市之间都有一条通道。
  • a,ba,b 两点间距离不大于 rr 则认定 a,ba,b 在同一个州。注意,如果 a,ba,b 处于同一个州,而 a,ca,c 也处于同一个州,则 b,cb,c 也处于这个州。
  • 给定 TT 组数据,对于每组输入数据包含 n,rn,r 两个数,nn 表示有 nn 个城市。接下来 nn 行,每行两个整数 xi,yix_i,y_i 表示第 ii 个点的坐标。输出州的个数、修建公路的最短距离、修建铁路的最短距离(保留整数)。
- 在 $Graphland$,有许多城市,但没有公路。你要在 $Graphland$ 中同一个州内的城市之间修建道路,并将使用铁路将不同州之间的城市连接起来。为了将修建公路和铁路的成本降到最低,政府还希望只修建必要的公路和铁路,以便在全国任何一对城市之间都有一条通道,求州的个数、修建公路、铁路的最短距离。
- 若 $a,b$ 两点间距离不大于 $r$ 则认定 $a,b$ 在同一个州。注意,如果 $a,b$ 处于同一个州,而 $a,c$ 也处于同一个州,则 $b,c$ 也处于这个州。
- 给定 $T$ 组数据,对于每组输入数据包含 $n,r$ 两个数,$n$ 表示有 $n$ 个城市。接下来 $n$ 行,每行两个整数 $x_i,y_i$ 表示第 $i$ 个点的坐标。输出州的个数、修建公路的最短距离、修建铁路的最短距离(保留整数)。
2020/8/11 14:41
加载中...