【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)。