一道比较妙的题。首先考虑建出补图来,那么发现,如果有两个点连通,就说明不能分在一个子图里面,恰好是二分图染色的流程。
之后考虑按补图的连通块 $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 ;
}
```