icpc南昌2019 B. A Funny Bipartite Graph

发表于 更新于 分类于 本文字数： 428 阅读时长 ≈ 2 分钟

题意为给定一个二分图，左右点数均为n，并给定左右相连的边，对这些边两端点满足,并且原图左边点的度数

现给定你一些限制条件并要求你选定一些点及其边，使得右边的点全部被覆盖到

状态压缩dp：

设以数组dp[i][j]其中表示二进制下中前位反应左边点的选取情况，后至位表示右边点的覆盖情况，注意判断是否满足的情况，便可不用三维数组来dp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
vi v[20], m(30);
LL dp[20][(1 << 20) - 1], tt, n, b[20];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> tt;
    f(sb, 1, tt)
    {
        string s;
        f(i, 1, 20)
        {
            v[i].clear();
            b[i] = 0;
        }
        cin >> n;
        f(i, 1, n)
        {
            cin >> s;
            f(j, 1, n)
            {
                if (s[j - 1] == '1')
                    v[i].pb(j);
            }
        }
        f(i, 1, n)
        {
            cin >> s;
            f(j, 1, n)
            {
                if (s[j - 1] == '1')
                    b[i] |= (1 << (n-j));
            }
        }
        f(i, 1, n) cin >> m[i];
        f(i, 1, n+1)
        {
            for (int j = 0; j < (1 << n); j++)
            {
                dp[i][j] = 2e8;
            }
        }
        dp[1][0] = 0;
        for (int i = 1; i <= n; i++)
        {
            for (int j = 0; j < (1 << n); j++)
            {
                if (dp[i][j] == 2e8)
                    continue;
                LL rs=(j&((1<<(n-i+1))-1)),ls=j&(((1<<n)-1)-((1<<(n-i+1))-1));
                if ((rs >> (n - i)) & 1)
                    dp[i + 1][j ^ (1 << (n - i))] = min(dp[i][j], dp[i + 1][j ^ (1 << (n - i))]);
                if (ls & b[i])
                {
                    continue;
                }
                for (LL ds = 1; ds < (1 << (v[i].size())); ds++)
                {
                    LL cost = 1, es = rs;
                    for (int k = 0; k < v[i].size(); k++)
                    {
                        if ((ds >> k) & 1)
                            cost *= m[i], es |= (1 <<(n- v[i][k]));
                    }
                    if (!((es >> (n - i)) & 1))
                        continue;
                    dp[i + 1][ls | es] = min(dp[i + 1][ls | es], dp[i][j] + cost);
                }
            }
        }
        LL ans = 2e8;
        for (int i = 0; i < (1 << n); i++)
        {
            ans = min(ans, dp[n+1][i]);
        }
        cout << (ans == 2e8 ? -1 : ans) << "\n";
    }
    return 0;
}