TCO15 Round 1A hard:Revmatching

多分本番中は問題分の意味がわからなかったと思うのでまぁやらなくてよかったかな。

問題:TopCoder Statistics - Problem Statement

解法:ホールの結婚定理というのがあるらしいです->(Hallの結婚定理とその証明 | 高校数学の美しい物語)。
この定理により,ある集合Aについてとなれば良いので,そのようになるもののうち取り除く辺の重みが最小のものが何か全探索すれば良い。
以下ソースコード

class Revmatching {
public:
    int smallest(vector <string> A) {
        int n = A.size();
        int mat[20][20];
        for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) mat[i][j] = A[i][j] - '0';
        int ret = 1e9;;
        for (int mask = 1; mask < (1<<n); mask++) {
            int cnt = __builtin_popcount(mask);
            vector<int> tmp(n);
            for (int i = 0; i < n; i++) {
                if ((mask>>i)&1) {
                    for (int j = 0; j < n; j++) {
                        tmp[j] += mat[i][j];
                    }
                }
            }
            sort(tmp.begin(), tmp.end());
            int p = 0;
            for (int i = 0; i < n-cnt+1; i++) {
                p += tmp[i];
            }
            ret = min(ret, p);
        }
        return ret;
    }
};