0%

洛谷 P6268 [SHOI2002]舞会

题意就不说了,其他题解写的都很好。

分析

明明这题第一个 tag 就是网络流,却没有一篇网络流的题解 qwq。

首先是染色,确定每对曾经跳过舞的学生的性别。

第一个坑,数据不保证无环,所以要这么写:

1
2
3
4
5
6
7
8
9
10
11
void color(int x, int c) {
col[x] = c;
vis[x] = true;
for (int i = head[x]; i; i = node[i].nxt) {
int v = node[i].v;
if (vis[v]) { // 如果你按照 v == f 写就会收获 MLE 若干
continue;
}
color(v, c ^ 1);
}
}

有人或许不理解怎么出现环,这里给出一组数据:

1
2
3
4
5
5 4
0 1
1 2
2 3
3 0

第二个坑,数据不保证每组前面一定是同种性别。于是你直接建模会收获 40 pts 的好成绩。

我的做法可能有点复杂,供参考。

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
auto* c = new Color();  // 完整代码最后会放在云剪贴板里

for (int i = 1; i <= m; i++) {
int x = read<int>(), y = read<int>();
x++, y++;
c->create(x, y);
c->create(y, x);
c->fm[i] = x;
c->to[i] = y;
}

for (int i = 1; i <= n; i++) {
if (!c->vis[i]) { // 数据不保证联通
c->color(i, 0);
}
}

auto* flow = new Flow(n + 20, s, t);
for (int i = 1; i <= m; i++) {
int x = c->fm[i], y = c->to[i];
if (c->col[x]) {
std::swap(x, y); // 前面的同学颜色不对,交换两位同学
}

flow->create(x, y, 1);
flow->create(y, x, 0);
}

最后注意数据并不保证图的联通,染色的时候不能只跑一遍。

建模

众所周知,网络流主要考建模。

这道题的建模不算很复杂,具体的分析可以看其他题解。

求最大独立集不好求,所以我们求最大匹配,转换为网络流上的最大流。输出答案的时候再拿总点数减一下就好了。

  • 不妨假设 \(u\) 的性别为 \(0\)\(v\) 的性别为 \(1\)
  • 建立容量为 \(1\) 的一条边 \((u,v)\)
  • 建立超级源点 \(S'\) ,超级汇点 \(T'\)
  • 对于每一个 \(u\) 建立容量为 \(1\) 的一条边 \((S',u)\)
  • 对于每一个 \(v\) 建立容量为 \(1\) 的一条边 \((v,T')\)

就好了啊 qwq。最后流向 \(t\) 的最大流就是二分图上的最大匹配。

还是不太理解的话可以看一下图:

最后附上完整代码