力扣每日一题---1601. 最多可达成的换楼请求数目

这次的周赛我就不讲了，比较简单，没什么好讲的。

?这题我们在思考的时候，是不是会发现一个问题，数据量这么小，会不会是暴搜呢？这个

问题我们先存着，等之后我们在讨论！！但是应该不是动归，动归和贪心题目数据量一般没这么小！！

先理解下题意，我们这题说有n个地点，并且本题最重要的一点就是n个地点中，比如1号点有3

人，a，b，c，那么当a,b,c去了其他点的话，那么必须要有其他人来1号点，也就是当前点离开的人数一定要等于到当前点的人数，否则就不成立。那么有了一个点有离开人数和到达人数，那么我们是不是想到并查集中的入度和出度，是不是对应离开人数和到达人数，当出度等于入度时条件成立，那么这题用并查集的入度和出度思想，是不是就可以判断当前状态合法，但是我们现在又有个问题，就是哪个状态才是符合最大这个条件，那么截止我们目前解决必要条件中的某一个条件就是怎么解决这个方案是否，那么第二个条件就是哪个状态才是符合最大。这就是我们的首要解决的问题了，我们在回到我们之前的数据量这个上面，这个数据量最多才20，那么是不是可以把状态全部枚举出来，算了一下复杂度是够的，那么解决必要条件的方法都已经知道了。

那么就可以通过算法这个充分条件去解决必要条件了，通过状态压缩来枚举状态。

class Solution {
public:
    int lowbit(int x) {
        return x & (-x);
    }

    int get_cnt(int x) {
        int res = 0;
        while (x) {
            x -= lowbit(x);
            res++;
        }
        return res;
    }

    int maximumRequests(int n, vector<vector<int>>& requests) {
        int m = requests.size();
        int ans = 0;
        auto check = [&](int x) -> bool {
            int din[21] = {0};  // 使用数组din和dou
            int dou[21] = {0};
            int sum = 0;
            for (int i = 0; i < 16; i++) {
                if (x >> i & 1) {
                    int a = requests[i][0], b = requests[i][1];
                    dou[a]++;
                    din[b]++;
                }
            }
            bool flag = false;
            for (int i = 0; i < n; i++) {
                if (dou[i] != din[i]) {
                    flag = true;
                }
            }
            return !flag;
        };

        for (int state = 0; state < (1 << m); state++) {
            int cnt = get_cnt(state);
            if (cnt <= ans) continue;
            if (check(state)) ans = cnt;
        }
        return ans;
    }
};