题解 AT4162 【[ARC099C] Independence】

皎月半洒花

2020-03-04 22:03:13

Solution

一道比较妙的题。首先考虑建出补图来,那么发现,如果有两个点连通,就说明不能分在一个子图里面,恰好是二分图染色的流程。 之后考虑按补图的连通块 $dp$。注意到如果补图中连通块 $A$ 和 $B$ 不连通,说明原图中所有点都连通。所以根本不需要考虑连通块之间的连边。具体的,设状态 $f_{i,j}$ 表示考虑了前 $i$ 个连通块,是否存在二分图集合的某一部(左部or右部)大小是 $j$ 。根据前面的性质这就是个背包。所以 `bitset` 优化转移一下即可。 ```cpp struct edge{ int to ; int next ; }E[N * N] ; int res ; int ctn ; int n, m ; int nienie ; int vis[N] ; int clr[N] ; int cnt[2] ; int head[N] ; bool A[N][N] ; bitset <N * N> ans ; void add(int x, int y){ to(++ ctn) = y ; next(ctn) = head[x] ; head[x] = ctn ; } void dfs(int x, int c){ vis[x] = 1 ; clr[x] = c ; cnt[c] ++ ; for (int k = head[x] ; k ; k = next(k)) if (!vis[to(k)]) dfs(to(k), c ^ 1) ; else if (clr[to(k)] == c) return nienie = 1, void() ; } int calc(int x){ return x * (x - 1) + (n - x) * (n - x - 1) ; } int main(){ cin >> n >> m ; ans[0] = 1 ; int u, v ; res = 1000000000 ; for (int i = 1 ; i <= m ; ++ i){ scanf("%d%d", &u, &v) ; A[u][v] = A[v][u] = 1 ; } for (int i = 1 ; i <= n ; ++ i) for (int j = 1 ; j <= n ; ++ j) if (!A[i][j] && (i ^ j)) add(i, j) ; for (int i = 1 ; i <= n ; ++ i){ if (!vis[i]){ cnt[0] = cnt[1] = 0 ; dfs(i, 0) ; ans = (ans << cnt[0]) | (ans << cnt[1]) ; } } if (nienie) return puts("-1"), 0 ; for (int i = 1 ; i <= n ; ++ i) if (ans[i]) res = min(res, calc(i)) ; return cout << res / 2 << endl, 0 ; } ```