题解：P14737 [ICPC 2021 Seoul R] Friendship Graphs

违规用户名1045961 · 2025-12-14 20:00:29 · 题解

看题 2min 想到思路，10min 切掉，洛谷第二个 AC，目前是最优解。

一个小组的学生都是在图中有连边的，不妨新建一个图，有边变没边，没边变有边，那么一个小组中的学生都是不能有连边的，有解当且仅当新图为二分图。

对于这个二分图的一个连通块，一边去 A 组，另一边去 B 组。假设两边点数之差为 qwq，那么 |A|-|B| 会加或减 qwq。

然后转化为，有一个人站在数轴上的 |A|-|B|，一开始在原点，每次会往左或右走确定的步长。最后走到的位置的绝对值就是答案。

用一个 bitset<N> b 记录这个人可能走到的位置，注意可以为负，可以将下标都加上 n。对于每个连通块 b=(b<<qwq)|(b>>qwq)。最后找到绝对值最小的 1 位即可。

:::success[代码]{open}

#include <bits/stdc++.h>
using namespace std;
using ll= long long;
const int N=2005;
int fa[N],siz[N];
int find(int u) {
    return fa[u]==u?u:(fa[u]=find(fa[u]));
}
void mg(int u,int v) {
    u=find(u),v=find(v);
    if(u==v) return;
    if(siz[u]<siz[v]) swap(u,v);
    fa[v]=u,siz[u]+=siz[v];
}
bool vis[N],edg[N][N];
int n,m;
int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    cin>>n>>m;
    for(int i=1;i<=n+n;i++)
        siz[fa[i]=i]=1;
    for(int u,v,i=1;i<=m;i++) {
        cin>>u>>v;
        edg[u][v]=edg[v][u]=1;
    }
    for(int i=1;i<n;i++)
        for(int j=i+1;j<=n;j++)
            if(!edg[i][j]) { // 种类并查集判二分图
                mg(i,j+n),mg(i+n,j);
                if(find(i)==find(i+n))
                    return cout<<-1,0;
            }
    bitset<N> b;
    b[n]=1;
    for(int i=1;i<=n;i++) if(!vis[i]) {
        int f1=find(i),f2=find(i+n);
        int qwq=0;
        for(int j=i;j<=n;j++) {
            if(f1==find(j)) qwq++,vis[j]=1;
            if(f2==find(j)) qwq--,vis[j]=1;
        }
        if(qwq<0) qwq*=-1;
        b=(b<<qwq)|(b>>qwq);
    }
    cout<<b._Find_next(n-1)-n;
}

:::