【Lintcode】707. Optimal Account Balancing

题目地址：

https://www.lintcode.com/problem/707/description

给定一个非负权有向图，其有 n n n个顶点和 m m m条边，给出所有的边的信息。每个顶点的“度”定义为其所有入边的权值总和与所有出边的权值总和之差。问整个图至少要加多少条边可以使得每个顶点的度都恰好为 0 0 0，边的权值可以任意赋值。注意点的编号不一定是 0 ∼ n − 1 0\sim n-1 0∼n−1，甚至不一定是连续的。

首先，对于一个这样的图而言，最多添加 n − 1 n-1 n−1条边是一定可以达到效果的。由于这样的图的所有点总度数一定等于 0 0 0，先略过所有度等于 0 0 0的点，然后依次从度不为 0 0 0的点出发，向另一个度不为 0 0 0的点连边，每个点的边权设置为能使得出发点的度为 0 0 0（边的方向也要做对应的调整）。由于所有点的度总和是 0 0 0，所以这样连接了 n − 1 n-1 n−1条边之后一定能使得每个点的度都为 0 0 0。

接下来考虑至少要加多少边。先用离散化的方式把每个点视为编号是 0 ∼ n − 1 0\sim n-1 0∼n−1。接下来用状态压缩，将 x x x的各个二进制位视为是这些点，二进制位取 1 1 1的时候说明含这个点，否则是不含。设 f [ x ] f[x] f[x]是在这个图里只考虑含 x x x的子图，至少需要加多少条边（这里的”子图“只含顶点，并且考虑每个顶点的度，不考虑边的情况）。设 g [ x ] g[x] g[x]是 x x x二进制表示里 1 1 1的个数。有两种情况，一种是最少加边方式只形成一个连通块，此时在度数总和是 0 0 0的情况下，最少加边数是 g [ x ] − 1 g[x]-1 g[x]−1（度数总和如果不是 0 0 0的话，无论怎么加边都不可能使得度数总和变成 0 0 0，从而更不可能让每个点的度变成 0 0 0）；另一种是最少加边方式形成了多个连通块，那么此时一定存在 x x x划分的两个子集，每个子集的度总和是 0 0 0，并且分别在两个子集内部加边，此时方案一定 g [ x ] − 1 g[x]-1 g[x]−1更优，可以枚举来找到加边最少的方案。综上，有： f [ x ] = min ⁡ { g [ x ] − 1 , min ⁡ y ⊂ x { f [ y ] + f [ x − y ] } } f[x]=\min\{g[x]-1,\min_{y\subset x}\{f[y]+f[x-y]\}\} f[x]=min{g[x]−1,y⊂xmin​{f[y]+f[x−y]}}代码如下：

import java.util.*;

public class Solution {
    /**
     * @param edges: a directed graph where each edge is represented by a tuple
     * @return: the number of edges
     */
    public int balanceGraph(int[][] edges) {
        // Write your code here
        Map<Integer, Integer> debt = new HashMap<>();
        for (int[] edge : edges) {
            int from = edge[0], to = edge[1], val = edge[2];
            debt.put(from, debt.getOrDefault(from, 0) - val);
            debt.put(to, debt.getOrDefault(to, 0) + val);
        }
        
        List<Integer> list = new ArrayList<>();
        for (Map.Entry<Integer, Integer> entry : debt.entrySet()) {
            if (entry.getValue() != 0) {
                list.add(entry.getValue());
            }
        }
        
        // 如果没有度非0的点，那么已经每个点度都是0了，不需要加边
        if (list.isEmpty()) {
            return 0;
        }
        
        int n = list.size();
        int[] f = new int[1 << n];
        Arrays.fill(f, 0x3f3f3f3f);
        
        for (int i = 1; i < 1 << n; i++) {
            int sum = 0, cnt = 0;
            // 求一下i的点数和总度数
            for (int j = 0; j < n; j++) {
                if ((1 << j & i) != 0) {
                    sum += list.get(j);
                    cnt++;
                }
            }
            
            // 如果i的总度数等于0，那么有可能通过加边使得每个点度都是0
            if (sum == 0) {
            	// 如果加边使得整个作为一个连通块，那么加边数是cnt - 1
                f[i] = cnt - 1;
                // 枚举i的子集
                for (int j = 1; j < i; j++) {
                    if ((i & j) == j) {
                    	// 枚举i划分为j和i - j两个子集的情况
                        f[i] = Math.min(f[i], f[j] + f[i - j]);
                    }
                }
            }
        }
        
        return f[(1 << n) - 1];
    }
}
           

时间复杂度 O ( 4 n ) O(4^n) O(4n)（实际不会这么慢，因为和为 0 0 0的子集数一般不会特别多，可以近似认为是 O ( n 2 n ) O(n2^n) O(n2n)复杂度），空间 O ( 2 n ) O(2^n) O(2n)。