洛谷P3153 [CQOI2009]跳舞

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

首先考虑建图，因为

每个男孩最多只愿意和个不喜欢的女孩跳舞，而每个女孩也最多只愿意和个不喜欢的男孩跳舞。

所以对于每个男孩女孩均要建一个辅助点，到该点的权值为，对于互相喜欢的男女孩相连，权值为，对于不喜欢的，则他们的辅助点相连，权值亦为。

接下来考虑源点到男孩与女孩到汇点的权值情况。

1.如果权值小于等于答案，计最大流为，则满足

2.权值大于答案，则有

所以，我可以用遍历权值从到的情况，得到答案，也可二分来做

坑点：忘记女孩也要满足小于等于

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
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
const int N = 2e4 + 86;

struct egdes
{
    int to, nxt, w;
} e[N * 2];
int hd[N * 2], cur[N * 2], tot = 1, st, en;
vi lv;
void add(int x, int y, int w)
{
    e[++tot] = (egdes){y, hd[x], w};
    hd[x] = tot;
}

int bfs()
{
    lv.assign(N, 0);
    memcpy(cur, hd, sizeof(hd));
    queue<int> q;
    q.push(st);
    lv[st] = 1;
    while (!q.empty())
    {
        int p = q.front();
        q.pop();
        for (int eg = hd[p]; eg; eg = e[eg].nxt)
        {
            int to = e[eg].to, vol = e[eg].w;
            if (vol && !lv[to])
            {
                lv[to] = lv[p] + 1;
                q.push(to);
            }
        }
    }
    return lv[en];
}

int dfs(int ss, int flow)
{
    if (ss == en)
        return flow;
    int r = flow;
    for (int eg = cur[ss]; eg && r; eg = e[eg].nxt)
    {
        cur[ss] = eg;
        int to = e[eg].to, vol = e[eg].w;
        if (vol && lv[to] == lv[ss] + 1)
        {
            int c = dfs(to, min(r, vol));
            r -= c;
            {
                e[eg].w -= c;
                e[eg ^ 1].w += c;
            }
        }
    }
    return flow - r;
}
int n, k;
vi rim[N];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> k;
    st = 6 * n + 86, en = st + 1;
    f(j, 1, n)
    {
        string s;
        cin >> s;
        //if(s.length()!=n)cout<<s.length();
        f(i, 1, n)
        {
            if (s[i - 1] == 'Y')
                rim[j].pb(i);
            else
                rim[j + n].pb(i);
        }
    }
    int l=0,r=n;
    while (l<r)
    {
        memset(hd, 0, sizeof(hd));
        tot = 1;
        int mid=(l+r+1)>>1;
        f(i, 1, n)
        {
            add(st, i, mid);
            add(i, st, 0);
            add(i, i + 2 * n, k);
            add(i + 2 * n, i, 0);
            add(i+4*n,i+n,k);
            add(i+n,i+4*n,0);
            add(i + n, en, mid);
            add(en, i + n, 0);
            for (auto it : rim[i])
            {
                add(i, it + n, 1);
                add(it + n, i, 0);
            }
            for (auto it : rim[i + n])
            {
                add(i + 2 * n, it +4* n, 1);
                add(it + 4*n, i + 2 * n, 0);
            }
        }
        LL ans = 0;
        while (bfs())
        {
            ans += dfs(st, 3e8);
        }
        if (mid * n == ans)
        {
            l=mid;
        }
        else r=mid-1;
    }
    cout <<l;
    return 0;
}