codeforce #773 div2 F （随机化 + SOSDP）

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

int main(){
    ios::sync_with_stdio(0);
    srand((unsigned)time(NULL));
    int n, m, T = 19; cin >> n >> m;
    const int mod = 1e9 + 7;
    vector<vector<int>> a(n, vector<int>(m + 1));
    for(int i = 0; i < n; i++){
        for(int j = 1; j <= m; j++) cin >> a[i][j];
        cin >> a[i][0];
    }

    LL tt = 80, ret = 2e10;
    while(tt--){
        vector<int> dp(1 << T, 2e9), b(n);
        int rd = rand(), rd2 = rand();
        for(int i = 0; i < n; i++){
            int bits = 0;
            for(int j = 1; j <= m; j++) bits |= (1 << (int)(1LL * a[i][j] * rd % mod * rd2 % mod % T));//随机化
            dp[bits] = min(a[i][0], dp[bits]), b[i] = bits;
        }
        for(int i = 0; i < (1 << T); i++)
            for(int j = 0; j < T; j++)
                if(i >> j & 1) dp[i] = min(dp[i], dp[i ^ (1 << j)]);//SOSDP

        int Tmax = (1 << T) - 1;

        LL ans = 2e10;
        for(int i = 0; i < n; i++) ans = min(ans, 0LL + a[i][0] + dp[Tmax ^ b[i]]);
        ret = min(ret, ans);
    }
    if(ret > 2e9) ret = -1;
    cout << ret;

    return 0;
}