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

分析

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

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

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

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);
    }
}

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

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

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

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\) 的最大流就是二分图上的最大匹配。

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

最后附上完整代码

Kris's Blog

洛谷 P6268 [SHOI2002]舞会

分析

建模