博客

D


e


s


c


r


i


p


t


i


o


n










$Description$

• 给定一个
  
  
  
  
  
  
  
  
  n
  
  
  
  
  
  
  
  
  
  
  $n$
  个点的二分图，每条边有一个边权。
• 找到一个边权和最小的边集，使得删掉这个边集之后不存在完备匹配。
• 
  
  
  
  
  
  
  
  
  n
  
  
  ≤
  
  
  20
  
  
  
  
  
  
  
  
  
  
  
  $n\le20$

S




o


l


u


t


i


o


n










$Solution$

根据Hall定理，不存在完备匹配当且仅当存在子集








S












$S$
，其中











|




S






|




<




|




N




(


S




)




|













$|S|<|N(S)|$
。

直接枚举子集贪心搞就好了。

// BEGIN CUT HERE

// END CUT HERE
#line 5 "Revmatching.cpp"
#include <bits/stdc++.h>
using namespace std;

const int N = 30;
const int INF = 1 << 20;

int mp[N][N];
int T[N], C[N], id[N];
int n, m, ans, c, s, U, res;
vector<int> from[N];

inline int BitCount(int x) {
  int cnt = 0;
  for (; x; x -= x & -x) ++cnt;
  return cnt;
}
inline bool cmp(int x, int y) {
  return C[x] < C[y];
}

class Revmatching {

public:
  int smallest(vector <string> A) {
    n = A.size(); m = A[0].size();
    ans = INF; U = 1 << n;
    for (int i = 0; i < n; i++)
      for (int j = 0; j < m; j++)
    mp[i][j] = A[i][j] - '0';
    for (int S = 1; S < U; S++) {
      c = 0; s = BitCount(S); res = 0;
      for (int i = 0; i < m; i++) {
    T[i] = C[i] = 0;
    from[i].clear();
    id[i] = i;
      }
      for (int i = 0; i < n; i++)
    if (S >> i & 1)
      for (int j = 0; j < m; j++)
        if (mp[i][j]) {
          if (!T[j]) ++c;
          ++T[j]; C[j] += mp[i][j];
          from[j].push_back(i);
        }
      for (int i = 0; i < m; i++)
    if (!T[i]) C[i] = INF;
      sort(id, id + m, cmp);
      for (int i = 0; i < m; i++) {
    if (c - i < s) break;
    res += C[id[i]];
      }
      ans = min(ans, res);
    }
    return ans;
  }

  // BEGIN CUT HERE
public:
  void run_test(int Case) { if ((Case == -1) || (Case == 0)) test_case_0(); if ((Case == -1) || (Case == 1)) test_case_1(); if ((Case == -1) || (Case == 2)) test_case_2(); if ((Case == -1) || (Case == 3)) test_case_3(); if ((Case == -1) || (Case == 4)) test_case_4(); if ((Case == -1) || (Case == 5)) test_case_5(); }
private:
  template <typename T> string print_array(const vector<T> &V) { ostringstream os; os << "{ "; for (typename vector<T>::const_iterator iter = V.begin(); iter != V.end(); ++iter) os << '\"' << *iter << "\","; os << " }"; return os.str(); }
  void verify_case(int Case, const int &Expected, const int &Received) { cerr << "Test Case #" << Case << "..."; if (Expected == Received) cerr << "PASSED" << endl; else { cerr << "FAILED" << endl; cerr << "\tExpected: \"" << Expected << '\"' << endl; cerr << "\tReceived: \"" << Received << '\"' << endl; } }
  void test_case_0() { string Arr0[] = {"1"}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arg1 = 1; verify_case(0, Arg1, smallest(Arg0)); }
  void test_case_1() { string Arr0[] = {"0"}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arg1 = 0; verify_case(1, Arg1, smallest(Arg0)); }
  void test_case_2() { string Arr0[] = {"44","44"}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arg1 = 8; verify_case(2, Arg1, smallest(Arg0)); }
  void test_case_3() { string Arr0[] = {"861","870","245"}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arg1 = 6; verify_case(3, Arg1, smallest(Arg0)); }
  void test_case_4() { string Arr0[] = {"01000","30200","11102","10001","11001"}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arg1 = 0; verify_case(4, Arg1, smallest(Arg0)); }
  void test_case_5() { string Arr0[] = {"0111101100","0001101001","1001001000","1000100001","0110011111","0011110100","1000001100","0001100000","1000100001","0101110010"}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arg1 = 1; verify_case(5, Arg1, smallest(Arg0)); }

  // END CUT HERE


};

// BEGIN CUT HERE
int main(void) {
  Revmatching ___test;
  ___test.run_test(-1);
  system("pause");
}
// END CUT HERE