【AT4162 [ARC099C]】 Independence 题解

Link:（洛谷）AT4162 [ARC099C] Independence

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

Solution

题意

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

1

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

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

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

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

---

感谢阅读。