[leetcode1601]最多可达成的换楼请求数目

https://leetcode-cn.com/problems/maximum-number-of-achievable-transfer-requests/

题目大意 最多20个楼和最多16个请求 每个请求都是从哪个楼出再到哪个楼 尽可能满足多的请求数 求最大请求数

正规思路是用网络流（不会 投机取巧用了二进制枚举 最长16个 因此可用二进制表示 0代表不选该方案 1代表选择该方案 选择完毕后进行check是否合法 检测方法为保证平衡（见代码

#include <bits/stdc++.h>
using namespace std;

class Solution
{
public:
  int getCnt(int t)
  {
    //计算t中包含1的个数
    int res = 0;
    for (int i = t; i > 0; i -= (i & -i))
      res++;
    return res;
  }
  bool check(int t, vector<vector<int>> &rs)
  {
    int arr[20]={0}; //最多20个楼
    int sum = 0;
    for (int i = 0; i < 16; i++)
    {
      //对于每一位进行判定
      if (((t >> i) & 1) == 1)
      {
        //如果这一位等于一 则选择该方案
        int a = rs[i][0], b = rs[i][1];
        //如果加上之后变成1 说明是从0变成1 不平衡度+1
        if (++arr[a] == 1)
          sum++;
        //如果减去之后变成0 说明是从1变成0 不平衡度-1
        if (--arr[b] == 0)
          sum--;
      }
    }
    //如果平衡 则该方案合法 否则该方案不合法
    return sum == 0;
  }

  int maximumRequests(int n, vector<vector<int>> &requests)
  {
    int m = requests.size(), ans = 0;
    for (int i = 0; i < (1 << m); i++)
    {
    
      int cnt = getCnt(i);
      if (cnt <= ans)
        continue;
      if (check(i, requests))
      {
        //如果合法 更新答案
        ans = cnt;
      }
    }
    return ans;
  }
};