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

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