校招笔试题解-施工队的最大利润

import java.util.*; /** * A国有n个城市，他们计划修建n1条长度为1的道路连接两个城市，城市规划已经给出，最终使得n个城市互相连通， * 从i城市到j城市有且只有一条唯一路径。 * <p> * 有一家施工队计划承包两段道路的修建工作，要求这两段道路不经过相同的城市(包括路径端点)， * 他们可以获得的利润是两段道路长度的乘积，现在要使得利润最大化，问最大能获得多少利润。 * <p> * 输入： * 输入共有n行，第一行包含一个整数n，表示城市的数量。（n<=200） * <p> * 接下来有n-1行，每行有两个整数,a,b,表示在a城市和b城市之间存在一条长度为1的道路。 * <p> * 输出： * 输出包含一行，表示最多可以获得的利润是多少 * <p> * 样例输入 * 4 * 1 2 * 2 3 * 3 4 * 样例输出 * 1 * <p> * 输入样例2 * 6 * 1 2 * 2 3 * 2 4 * 5 4 * 6 4 * <p> * 输出样例2 * 4 * <p> * 样例解释 * 样例2应该选取1-2-3和5-4-6,这样一来两条道路的长度都为2，利润最大为2*2 * * @author Lean.Li * @date 2018/9/10 */ public class Main { public static void main(String[] args) { Scanner input = new Scanner(System.in); int n = input.nextInt(); boolean[][] arr = new boolean[n + 1][n + 1]; HashMap<Integer, List<HashSet<Integer>>> list = new HashMap<>(n - 1); for (int i = 1; i < n; i++) { int a = input.nextInt(); int b = input.nextInt(); arr[a][b] = arr[b][a] = true; } input.close(); findAllPaths(arr, n, list); int max = getMaxProfile(list, n); System.out.println(max); } /** * 找到所有路径：从各个节点出发递归找到所有路径 * * @param arr * @param n * @param list */ private static void findAllPaths(boolean[][] arr, int n, HashMap<Integer, List<HashSet<Integer>>> list) { for (int i = 1; i <= n; i++) { getNext(arr, i, list, new HashSet<>()); } } /** * 递归获取路径 * * @param arr * @param index * @param list * @param set */ private static void getNext(boolean[][] arr, int index, HashMap<Integer, List<HashSet<Integer>>> list, HashSet<Integer> set) { for (int i = 1; i < arr.length; i++) { if (arr[index][i]) { if (set.contains(i)) { list.computeIfAbsent(set.size(), k -> new ArrayList<>()); list.get(set.size()).add(new HashSet<>(set)); } else { set.add(i); getNext(arr, i, list, set); set.remove(i); } } } } /** * 求出最大利润 * * @param list * @param n * @return */ private static int getMaxProfile(HashMap<Integer, List<HashSet<Integer>>> list, int n) { int k = n / 2; int m = n - k; int max = 0; List<HashSet<Integer>> empty = new ArrayList<>(0); while (k > 1 && m < n) { List<HashSet<Integer>> list1 = list.getOrDefault(k, empty); List<HashSet<Integer>> list2 = list.getOrDefault(m, empty); if (list1.isEmpty() || list2.isEmpty()) { k--; m++; continue; } for (HashSet<Integer> s1 : list1) { // 求 s1 的补集 s2 HashSet<Integer> s2 = new HashSet<>(); for (int i = 1; i <= n; i++) { if (!s1.contains(i)) { s2.add(i); } } // 找 s2 是否存在 if (list2.contains(s2)) { int profile = (k - 1) * (m - 1); if (profile > max) { max = profile; } } } k--; m++; } return max; } }