【AT4162 [ARC099C]】 Independence 题解

Link:（洛谷）AT4162 [ARC099C] Independence

首先在此感谢 @kymru 大佬提供的学术支持。

UPDATE

• 2022 - 10 - 17：更改了文章中一处表达有误的地方并补充完善了第一部分的说明。

Solution

题意

给一张图，N 个点，M 条边，要求将图分成两个团，使得两个顶点都在同一个团中的边最少，求最小值。（团是一个两两之间有边的顶点集合。）

1

发现把所有节点分层两个团的本质就是对这些点进行黑白染色。设最后染成黑色的节点数为 a，白色的节点数为 b，则最终输出的答案即为 \frac{a\times(a-1)+b\times(b-1)}{2}。

发现直接对原图上手太复杂了，那些边也很难处理。所以考虑对原图建它的补图。根据补图的定义，知道在补图中有一条边连接的两个节点在原图中不直接联通。所以，这样一来就把题目中“团是一个两两之间有边的顶点集合”转化为“集合内的节点两两不直接联通”。说到这里，显然，就变成将补图转化为一个二分图了。

需要注意的是，在对原图建了补图之后，可能会出现若干个连通块，即连通块（二分图）的数量大于等于 1。

在一个二分图内，试将其某一部点都染成白色，另一部点都染成黑色。而这两部点就是答案所求的两个团各自的一部分。但是，原图的补图会有多个二分图，即不止一个连通块。那如何确定每一个二分图左右部点各自所染的颜色呢？

2

回过头，答案的最终形式是 \frac{a\times(a-1)+b\times(b-1)}{2}，运用简单小学数学知识，可以将它的分子部分转化为 (a+b)\times(a+b-1)-2ab，即 n\times(n-1)-2ab。再运用小学数学知识，知道“和一定，差小积大”，所以目标就变成让 a 和 b 的差尽可能小。

因此，在遍历一个连通块将其转化为一二分图的过程中，记录下每个二分图它的左右部点数量的差值，并全部相加，记为 sum。接着要做的就是适当分配这些差值（分成两部分 x 和 y），使这两部分的和，它们两的差尽可能小。绕这么多，其实就是为了 a 和 b 的差尽可能小。

显然，我们想要 x 和 y 都尽可能接近 \frac{sum}{2}。这里运用到最优性转可行性的方法——背包 dp。

3

通过简单背包，可以求得 x 和 y 的最小差值，即 a 和 b 的最小差值。同时，已知 a 与 b 的和（即 n），组合起来，就又是一个小学数学知识，就成为了一个简单的和差问题。往下的解和差问题就不多说了。

至此，此题被完美解决，复杂度可过。

Code

#include<bits/stdc++.h>
using namespace std;

#define rep(i, a, b) for(register int i = a; i <= b; ++i)
#define per(i, a, b) for(register int i = a; i >= b; --i)
const int maxn = 705, maxm = 500005;
int n, m, sum;
bool flg, g[maxn][maxn], f[maxn];
int cnt, hd[maxn];
struct edge{
    int to, nxt;
}e[maxm];
int del[maxn], col[maxn], cur;
int u, v, tmp;

inline void add(int u, int v){
    e[++cnt] = (edge){v, hd[u]}, hd[u] = cnt;
}

inline void dfs(int u, int t){
    if(flg) return;
    del[t] += (col[u] == 1 ? 1 : -1);
    for(int v, i = hd[u]; i; i = e[i].nxt)
        if(!col[v = e[i].to])
            col[v] = 3 - col[u], dfs(v, t);
        else if(col[v] == col[u]){
            flg = 1; return;
        }
}

int main(){
    scanf("%d%d", &n, &m);
    rep(i, 1, m)
        scanf("%d%d", &u, &v), g[u][v] = g[v][u] = 1;
    rep(i, 1, n) rep(j, 1, n)
        if(!g[i][j] and i != j) add(i, j); 
    rep(i, 1, n){
        if(!col[i])
            col[i] = 1, dfs(i, ++cur),
            del[cur] = abs(del[cur]), sum += del[cur];
        if(flg){
            printf("-1\n"); return 0;
        }
    }
    f[0] = 1;
    rep(i, 1, cur) per(j, sum / 2, del[i])
        f[j] |= f[j - del[i]];
    per(i, sum / 2, 0) if(f[i]){
        tmp = i; break;
    }
    tmp = abs(sum - tmp * 2);
    int a = (n + tmp) >> 1, b = (n - tmp) >> 1;
    printf("%d\n", a * (a - 1) / 2 + b * (b - 1) / 2);
    return 0;
} 

感谢阅读。