ZOJ 3760 Treasure Hunting(网络流)

题目大意

在2D平面上有 $N$ 个藏宝点,每个点的坐标为 $(x_i, y_i)$ ,价值为 $x_i$ $AND$ $y_i$ 。
现要求选择权值和最大的一些点,且点集 $T$ 满足:
$$ \forall(x_i, y_i)(x_j, y_j)(i \not= j) \in T, gcd(x_i \oplus y_i \oplus x_j \oplus y_j, P) > 1 $$
$P$ 是偶数,且 $\oplus$ 代表异或。
求点集 $T$。
$ (1 \le N \le 500, 2 \le P \le 10^{9}, 0 \le x_i, y_i \le 10^{9})$
$ (\forall i, j, x_i \oplus y_i \oplus x_j \oplus y_j > 0)$


解题思路

二分图最大点权独立集

若直接根据点集条件将不满足条件的点连边,则无法确定是否是二分图,没办法进行建图求解。
Ps: 一般图的最大点权独立集是NP困难的。
考虑到这点,我们还是从题目入手,发现 $P$ 一定是偶数,我们分别计算 $x_i \oplus y_i$ 的值。
由于奇数 $\oplus$ 奇数 $=$ 偶数偶数 $\oplus$ 偶数 $=$ 偶数奇数 $\oplus$ 偶数 $=$ 奇数,显然,不满足条件的边只能是第三种情况,否则gcd值至少为2。
因此可证此图必是二分图(不可能有奇数环)。由此将 $x_i \oplus y_i$ 为奇数的当成 $X$ 集合,为偶数的当成 $Y$ 集合,直接跑网络流就可以了。(具体建图见下方知识扩展)

代码如下:

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
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <queue>
#include <map>
#include <set>

using namespace std;

typedef long long ll;

const int MAXN = 5e2 + 10;
const int MAXM = 1e5 + 10;
const int INF = 0x3f3f3f3f;

struct edge {
int to, cap, next;
edge( int to = 0, int cap = 0, int next = 0 ) : to(to), cap(cap), next(next) {}
} G[MAXM << 1];
int n, p;
int x[MAXN], y[MAXN];
int v[MAXN];
int tot, head[MAXN], cur[MAXN];
int d[MAXN];

void add_edge(int u, int v, int cap)
{

G[tot] = edge(v, cap, head[u]);
head[u] = tot++;
G[tot] = edge(u, 0, head[v]);
head[v] = tot++;
}
bool bfs(int s, int t)
{

memset(d, -1, sizeof(d));
queue<int> que;
que.push(s);
d[s] = 0;

while( !que.empty() )
{
int u = que.front(); que.pop();
for( int i = head[u]; ~i; i = G[i].next )
{
edge e = G[i];
if( e.cap > 0 && d[e.to] == -1 )
{
d[e.to] = d[u] + 1;
que.push(e.to);
}
}
}
return ~d[t];
}
ll dfs(int u, int t, int f)
{

if( u == t ) return f;
ll sum = 0;
for( int &i = cur[u]; ~i; i = G[i].next )
{
edge e = G[i];
if( e.cap > 0 && d[e.to] == d[u] + 1 )
{
ll tmp = dfs(e.to, t, min(e.cap, f));
if( tmp > 0 )
{
G[i].cap -= tmp;
G[i ^ 1].cap += tmp;
f -= tmp;
sum += tmp;
}
}
}
return sum;
}
ll Dinic(int s, int t)
{

ll sum = 0;
while( bfs(s, t) )
{
memcpy(cur, head, sizeof(head));
sum += dfs(s, t, INF);
}
return sum;
}
int gcd(int a, int b)
{

return b ? gcd(b, a % b) : a;
}
void init()
{

tot = 0;
memset(head, -1, sizeof(head));
}
int main()
{

while( ~scanf("%d %d", &n, &p) )
{
init();
int s = 0, t = n + 1;
ll ans = 0;
for( int i = 1; i <= n; ++ i )
{
scanf("%d %d", x + i, y + i);
v[i] = x[i] ^ y[i];
ans += x[i] & y[i];
if( v[i] & 1 ) add_edge(s, i, x[i] & y[i]);
else add_edge(i, t, x[i] & y[i]);
}
for( int i = 1; i <= n; ++ i )
{
for( int j = 1; j < i; ++ j )
{
if( gcd(v[i] ^ v[j], p) <= 1 )
{
if( v[i] & 1 ) add_edge(i, j, INF);
else add_edge(j, i, INF);
}
}
}
printf("%lld\n", ans - Dinic(s, t));
}

return 0;
}


知识扩展

二分图最大点权独立集

概念:给出一个二分图,每个结点上有一个非负权值。要求选出一些点,使得这些点之间没有边相连,且权值和最大。

做法:在二分图的基础上添加源点S和汇点T,然后从S向所有X集合中的点连一条边,所有Y集合中的点向T连一条边,容量均为该点的权值,X结点与Y结点之间的边的容量均为无穷大。这样,对于该图中的任意一个割,将割中的边对应的结点删掉就是一个符合要求的解,权和为所有权和减去割的容量。因此,只需要求出最小割,就能求出最大权和。

二分图最小点权覆盖集

概念:给出一个二分图,每个结点上有一个非负权值。要求选出一些点,使得这些点覆盖所有的边,且权值和最小。

做法:与求二分图最大点权独立集相同。最小点权覆盖集的总权值 + 最大点权独立集的总权值 = 图的总权值。


Brain Power

若给出的点有负权值,那应该怎么求?

显然对于二分图最大点权独立集来说,负权值的点没有意义,直接不考虑。那求二分图最小点权覆盖集时呢?

头脑风暴下吧!

如果您觉得这篇博文对您有所帮助,可以考虑请我吃颗糖哦!