P2423 [HEOI2012]朋友圈

发表于 | 阅读数

A国：每个人都有一个友善值，当两个A国人的友善值 $a,b$，如果 $a\text{ xor}\text{ }b \bmod 2=1$，那么这两个人都是朋友，否则不是；

B国：每个人都有一个友善值，当两个B国人的友善值 $a,b$，如果 $a\text{ xor}\text{ }b \bmod 2=0$ 或者$a\text{ }or\text{ }b$ 化成二进制有奇数个 $1$，那么两个人是朋友，否则不是朋友。

求最大团，给$A,B$的关系。

$A$国显然$0,1,2$人。

然后考虑如何计算枚举到的$B$国的最大团。

可以看出$B$的补图就是一个分奇偶的二分图。

二分图的最大团=补图的最大独立集。，最大独立集=所有顶点数-最小顶点覆盖，

跑个最大流即可。或者时间戳匈牙利。各种剪枝加一加很快的。

代码 
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
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207


#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pii pair<int, int>
#define mk make_pair
const int N = 1e6 + 10;
const int mod = 1e9 + 7;
const int INF = 1e9;
struct Edge
{
    int to, w, nxt;
    Edge() {}
    Edge(int v, int c, int t) : to(v), w(c), nxt(t) {}
};
const int EN = 2e6 + 10;
const int EM = 2e6 + 10;
struct Dinic
{

    Edge e[EM << 1];
    int head[EN], scnt, d[EN], cur[EN];
    pii pre[EN];
    int maxn;
    Dinic() { scnt = 1; }
    void addEdge(int u, int v, int w)
    {
        e[++scnt] = Edge(v, w, head[u]);
        head[u] = scnt;
        e[++scnt] = Edge(u, 0, head[v]);
        head[v] = scnt;
    }
    void init(int n)
    {
        maxn = n;
    }
    void clear()
    {
        // memset(head, 0, sizeof(head));
        // memset(d, 0, sizeof(d));

        for (int i = 0; i <= maxn; i++)
            head[i] = d[i] = cur[i] = 0, pre[i] = mk(0, 0);
        scnt = 1;
    }
    bool bfs(int s, int t)
    {
        queue<int> q;
        for (int i = 0; i <= maxn; i++)
            d[i] = 0;
        q.push(s);
        d[s] = 1;
        while (!q.empty())
        {
            int x = q.front();
            q.pop();
            for (int i = head[x]; i; i = e[i].nxt)
            {
                int to = e[i].to;
                if (!d[to] && e[i].w)
                {
                    d[to] = d[x] + 1;
                    q.push(to);
                    if (to == t)
                        return true;
                }
            }
        }
        return false;
    }
    int dfs(int x, int t, int flow)
    {
        if (x == t)
            return flow;
        int res = 0;
        for (int i = cur[x]; i; i = e[i].nxt)
        {
            cur[x] = i;
            int to = e[i].to;
            if (d[to] == d[x] + 1 && e[i].w)
            {
                int dis = dfs(to, t, min(flow, e[i].w));
                if (dis)
                {
                    e[i].w -= dis;
                    e[i ^ 1].w += dis;
                    flow -= dis;
                    res += dis;
                    if (!flow)
                        return res;
                }
            }
        }
        return res;
    }
    int Maxflow(int s, int t)
    {
        int ans = 0;
        while (bfs(s, t))
        {
            memcpy(cur, head, sizeof(head));
            ans += dfs(s, t, INF);
        }
        return ans;
    }
} dc;

int read()
{
    int x = 0, f = 1;
    char c = getchar();
    while (c < '0' || c > '9')
    {
        if (c == '-')
            f = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9')
        x = (x << 1) + (x << 3) + c - '0', c = getchar();
    return x * f;
}
int a[N], b[N];
vector<int> g[N];
vector<int> p[2];
int vis[N], id[N];
vector<pii> e;
int A, B, M, ans;
void solve(int x, int y, int z)
{
    for (int i = 1; i <= B; i++)
        vis[i] = id[i] = 0;
    for (int o : g[x])
        vis[o]++;
    for (int o : g[y])
        vis[o]++;
    int cnt = 0;

    for (int i = 1; i <= B; i++)
    {
        if (vis[i] == z)
            id[i] = ++cnt;
    }
    //cout << x << " " << y << " " << cnt << endl;
    if (cnt + z <= ans)
        return;
    int s = ++cnt, t = ++cnt;
    //cout << cnt << endl;
    dc.init(cnt);
    for (int x : p[0])
        if (id[x])
            dc.addEdge(s, id[x], 1);
    for (int x : p[1])
        if (id[x])
            dc.addEdge(id[x], t, 1);
    for (pii now : e)
    {
        int x = now.first, y = now.second;
        if (id[x] == 0 || id[y] == 0)
            continue;
        dc.addEdge(id[x], id[y], 1);
    }

    ans = max(ans, cnt - 2 - dc.Maxflow(s, t) + z);
    dc.clear();
}

int main()
{
    int T = read();
    while (T--)
    {

        A = read(), B = read(), M = read();
        ans = 0;
        p[0].clear(), p[1].clear();
        for (int i = 1; i <= A; i++)
            a[i] = read(), g[i].clear();
        for (int i = 1; i <= B; i++)
            b[i] = read(), p[b[i] & 1].push_back(i);

        for (int i = 1; i <= M; i++)
        {
            int x = read(), y = read();
            g[x].push_back(y);
        }

        for (int i : p[0])
            for (int j : p[1])
            {
                if (!((__builtin_popcount((b[i] | b[j]))) & 1))
                    e.push_back(mk(i, j));
            }
        //solve(1, 2, 2);
        solve(0, 0, 0);
        for (int i = 1; i <= A; i++)
            solve(i, 0, 1);
        for (int i = 1; i <= A; i++)
            for (int j = i + 1; j <= A; j++)
                if ((a[i] ^ a[j]) & 1)
                {

                    solve(i, j, 2);
                }
        printf("%d\n", ans);
    }
}