题目描述
最先的思路
结果说内存超限
Java 代码
import java.util.Scanner;
class Main{
static int[][] biao;
static Scanner sc = new Scanner(System.in);
static int zhijing,Point;
public static void main(String[] args) {
int n=sc.nextInt();
luru(n);
dfs(1,n,new boolean[n+1],0);
dfs(Point,n,new boolean[n+1],0);
System.out.println(getValue(zhijing));
}
public static void luru(int n) {
biao=new int[n+1][n+1];
int a,b,w;
for(int i=1;i<n;i++) {
a=sc.nextInt();b=sc.nextInt();w=sc.nextInt();
biao[a][b]=biao[b][a]=w;
}
}
public static void dfs(int nowPoint,int endPoint,boolean[] flag,int nowW) {
flag[nowPoint]=true;
if(nowW>zhijing) {
zhijing=nowW;
Point=nowPoint;
}
for(int i=1;i<=endPoint;i++) {
if(biao[nowPoint][i]==0||flag[i])continue;//当当前节点与第i个结点不相连时或第i个结点已经考虑过时跳过本次循环
//执行到下面证明当前节点与第i个结点相连且第i个结点还未考虑过
dfs(i,endPoint,flag,nowW+biao[nowPoint][i]);
flag[i]=false;
}
}
public static long getValue(int distance) {
int result=0;
for(int i=1;i<=distance;i++) {
result+=10+i;
}
return result;
}
}
后来的优化
参考了别人的树的直径.两次dfs求出树的直径。
Java代码
import java.util.Scanner;
public class Main {
static Scanner sc = new Scanner(System.in);
static int zhijing,Point;
static City[] citys;
public static void main(String[] args) {
int n = sc.nextInt();
luru(n);
dfs(1,n,new boolean[n+1],0);
dfs(Point,n,new boolean[n+1],0);
System.out.println(getValue(zhijing));
}
public static void luru(int n) {
citys = new City[n+1];
for(int i=1;i<=n;i++)citys[i]=new City();
int a,b,w;
for(int i=1;i<n;i++) {
a=sc.nextInt();b=sc.nextInt();w=sc.nextInt();
citys[a].toCity[citys[a].length]=b;citys[b].toCity[citys[b].length]=a;
citys[a].lujing[citys[a].length++]=w;citys[b].lujing[citys[b].length++]=w;
}
}
public static void dfs(int nowCity,int endCity,boolean[] flag,int nowW) {
flag[nowCity]=true;
if(zhijing<nowW) {zhijing=nowW;Point=nowCity;}
for(int i=0;i<citys[nowCity].length;i++) {
if(flag[citys[nowCity].toCity[i]])continue;
dfs(citys[nowCity].toCity[i],endCity,flag,nowW+citys[nowCity].lujing[i]);
flag[citys[nowCity].toCity[i]]=false;
}
}
public static long getValue(int distance) {
long result=0;
for(int i=1;i<=distance;i++) {
result+=10+i;
}
return result;
}
}
class City{
int length=0;
int[] toCity=new int[20];
int[] lujing=new int[20];
}