牛牛铺路
-
- 题目分析过程
- 完整代码
- 附上c++代码
题目分析过程
首先需要定义找到来连接两个城市的最短路径，long get()
给定下City1:x1、y1、x2、y2.City2:x3、y3、x4、y4.(左下角、右上角）
可知：
连接两个城市x方向最短路径：max(x1、x3)-min(x2、x4)
连接两个城市x方向最短路径：max(y1、y3)-min(y2、y4)
连接两个城市的最短外径：【max(x1、x3)-min(x2、x4)】+【max(y1、y3)-min(y2、y4)】
public static int get(Node a, Node b){
int x1 = a.x1, x2 = a.x2, y1 = a.y1, y2 = a.y2;
int x3 = b.x1, x4 = b.x2, y3 = b.y1, y4 = b.y2;
int dist_x = Math.max((int)0, Math.max(x1, x3) - Math.min(x2, x4));
int dist_y = Math.max((int)0, Math.max(y1, y3) - Math.min(y2, y4));
return dist_x + dist_y;
}
然后开始输入参数
此时按照输入案例：
3
0 0 1 1
2 2 3 3
4 4 5 5
可知每次需要输入四位元素，故定义城市对象：
class Node{
int x1, y1, x2, y2;
}
定义两城市路径对象：
class Edge
{
int a, b;
int c;
}
输入：
public static void main(String[] args){
fouth f=new fouth();
Scanner sc = new Scanner(System.in);
int n;
n = sc.nextInt();
Node [] y=new Node[n];
for(int i=0;i<n;i++){
y[i] = new Node();
y[i].x1 = sc.nextInt();
y[i].y1 = sc.nextInt();
y[i].x2 = sc.nextInt();
y[i].y2 = sc.nextInt();
//System.out.println(y[i].x1);
}
建立城市路径集：然后按照路径大小排序：
// 建边
int cnt = 0;
Edge [] e=new Edge[(n*(n-1))/2];
for(int i = 0; i <n; i++)
for(int j = 0; j < i; j++)
{
int dist = get(y[i], y[j]);
e[cnt]=new Edge();
e[cnt].a = i;
e[cnt].b=j;
e[cnt].c=dist;
System.out.println(e[cnt].a+" "+e[cnt].b+" "+e[cnt].c);
cnt++;
}
int res = 0;
f.ageSort(e);//按照路径大小排序
for(int i=0;i<n*(n-1)/2;i++){
System.out.println(e[i].a+" "+e[i].b+" "+e[i].c);
}
// 并查集初始化
p=new int[n];
for(int i = 0; i <n; i++){
p[i] = i;
}
当某个城市出现时，将其对应的p[]值定为定值：
未出现的城市被编入路径中：
static int find(int x)
{
if (p[x] != x)
p[x] = find(p[x]);
return p[x];
}
for(int i = 0; i < cnt; i++)
{
int a = e[i].a, b = e[i].b;
int c = e[i].c;
if(find(a) != find(b))
{
p[find(a)] = find(b);
res += c;
}
}
System.out.println(res);
完整代码
package wangyi2021;
import java.util.*;
class Node{
int x1, y1, x2, y2;
}
class Edge
{
int a, b;
int c;
}
public class fouth {
static int N=1010,M=N*N;
static int n,p[];
// public class dict{
// Node node;
// }
public static int get(Node a, Node b){
int x1 = a.x1, x2 = a.x2, y1 = a.y1, y2 = a.y2;
int x3 = b.x1, x4 = b.x2, y3 = b.y1, y4 = b.y2;
int dist_x = Math.max((int)0, Math.max(x1, x3) - Math.min(x2, x4));
int dist_y = Math.max((int)0, Math.max(y1, y3) - Math.min(y2, y4));
return dist_x + dist_y;
}
static int find(int x)
{
if (p[x] != x)
p[x] = find(p[x]);
return p[x];
}
Comparator<Edge> comparatorAge =new Comparator <Edge>(){
public int compare(Edge p1,Edge p2){
if (p1.c>p2.c)
return 1;
else if (p1.c<p2.c)
return -1;
else
return 0;
}
};
public Edge [] ageSort(Edge[] s){
Arrays.sort(s,comparatorAge);
return s;
}
public static void main(String[] args){
fouth f=new fouth();
Scanner sc = new Scanner(System.in);
int n;
n = sc.nextInt();
Node [] y=new Node[n];
for(int i=0;i<n;i++){
y[i] = new Node();
y[i].x1 = sc.nextInt();
y[i].y1 = sc.nextInt();
y[i].x2 = sc.nextInt();
y[i].y2 = sc.nextInt();
//System.out.println(y[i].x1);
}
// 并查集初始化
p=new int[n];
for(int i = 0; i <n; i++){
p[i] = i;
}
// 建边
int cnt = 0;
Edge [] e=new Edge[(n*(n-1))/2];
for(int i = 0; i <n; i++)
for(int j = 0; j < i; j++)
{
int dist = get(y[i], y[j]);
e[cnt]=new Edge();
e[cnt].a = i;
e[cnt].b=j;
e[cnt].c=dist;
System.out.println(e[cnt].a+" "+e[cnt].b+" "+e[cnt].c);
cnt++;
}
int res = 0;
f.ageSort(e);
for(int i=0;i<n*(n-1)/2;i++){
System.out.println(e[i].a+" "+e[i].b+" "+e[i].c);
}
for(int i = 0; i < cnt; i++)
{
int a = e[i].a, b = e[i].b;
int c = e[i].c;
if(find(a) != find(b))
{
p[find(a)] = find(b);
res += c;
}
}
System.out.println(res);
}
}
附上c++代码
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
//using LL = long long;
typedef long long LL;
const int N = 1010, M = N * N;//定义了一个 N， M
int n;//定义了个n
int p[N];//定义了个p[n]
struct Node//定义节点
{
int x1, y1, x2, y2;//节点包含四个元素
}nodes[N];//节点名为这个
struct Edge//定义了edge(节点） 包含以下元素
{
int a, b;
LL c;
Edge() : a(), b(), c() {}
Edge(int a, int b, LL c) : a(a), b(b), c(c) {}
bool operator< (const Edge& w) const{
return c < w.c;
}
}e[M];
int find(int x)
{
if (p[x] != x)
p[x] = find(p[x]);
return p[x];
}
LL get(Node& n1, Node& n2)
{
LL x1 = n1.x1, x2 = n1.x2, y1 = n1.y1, y2 = n1.y2;
LL x3 = n2.x1, x4 = n2.x2, y3 = n2.y1, y4 = n2.y2;
//cout << x1 << ' ' << x2 << ' ' << x3 << ' ' << x4 << endl;
LL dist_x = max((LL)0, max(x1, x3) - min(x2, x4));
LL dist_y = max((LL)0, max(y1, y3) - min(y2, y4));
// cout << dist_x << ' ' << dist_y << endl;
return dist_x + dist_y;
}
int main()
{
scanf("%d", &n);
for(int i = 1; i <= n; i++)
{
int x1, y1, x2, y2;
scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
nodes[i] = {x1, y1, x2, y2};
}
// 并查集初始化
for(int i = 1; i <= n; i++)
p[i] = i;
// 建边
int cnt = 0;
for(int i = 1; i <= n; i++)
for(int j = 1; j < i; j++)
{
LL dist = get(nodes[i], nodes[j]);
//cout << i << ' ' << j << ' ' << dist << endl;
e[cnt++] = {i, j, dist};
cout << cnt << ' '<< endl;
}
for(int i=0;i<n*(n-1)/2;i++){
cout << e[i].a << ' ' << e[i].b << ' ' << e[i].c << endl;
}
// kruskal 求最小生成树
LL res = 0;
sort(e, e + cnt);
for(int i=0;i<n*(n-1)/2;i++){
cout << e[i].a << ' ' << e[i].b << ' ' << e[i].c << endl;
}
for(int i = 0; i < cnt; i++)
{
int a = e[i].a, b = e[i].b;
LL c = e[i].c;
if(find(a) != find(b))
{
p[find(a)] = find(b);
res += c;
}
}
cout << res << endl;
return 0;
}
![美团点评 2019校园招聘 后台开发方向职位编程题-2018.09.06[图]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)