【题解】10.31模拟赛T2：蓝精灵的请求

我的做法是乱搞，跟std完全不一样
首先如果两个点之间没有边，那么这两个点肯定属于不同的点集
可以$bfs$处理肯定属于同一点集的点
然后处理出一些点集，整体思想点集之间如果可以合并成同一个点集就连一条边
跑暴力$dfs$求得答案

Code：

#include <bits/stdc++.h>
#define maxn 710
using namespace std;
int n, m, flag[maxn][maxn], Flag[maxn][maxn], num, color[maxn], type[maxn];
int cnt[maxn][2], a[maxn][2][maxn], can[maxn][2][maxn][2], ans;
queue <int> q;

inline int read(){
	int s = 0, w = 1;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') w = -1;
	for (; isdigit(c); c = getchar()) s = (s << 1) + (s << 3) + (c ^ 48);
	return s * w;
}

bool check(int x, int p, int y, int q){
	for (int i = 1; i <= cnt[x][p]; ++i)
		for (int j = 1; j <= cnt[y][q]; ++j)
			if (Flag[a[x][p][i]][a[y][q][j]]) return 0;
	return 1;
}

void dfs(int t, int sum1, int sum2){
	if (t > num) ans = min(ans, sum1 * (sum1 - 1) / 2 + sum2 * (sum2 - 1) / 2); else{
		if (can[t - 1][0][t][0] && can[t - 1][1][t][1]) dfs(t + 1, sum1 + cnt[t][0], sum2 + cnt[t][1]);
		if (can[t - 1][0][t][1] && can[t - 1][1][t][0]) dfs(t + 1, sum2 + cnt[t][0], sum1 + cnt[t][1]);
	}
}

int main(){
	freopen("request.in", "r", stdin);
	freopen("request.out", "w", stdout);
	n = read(), m = read();
	for (int i = 1; i <= m; ++i){
		int x = read(), y = read();
		flag[x][y] = flag[y][x] = 1;
	}
	for (int i = 1; i <= n; ++i)
		for (int j = 1; j <= n; ++j)
			if (i != j && !flag[i][j]) Flag[i][j] = Flag[j][i] = 1;
	for (int i = 1; i <= n; ++i)
		if (!color[i]){
			color[i] = ++num, type[i] = 1;
			q.push(i);
			while (!q.empty()){
				int u = q.front(); q.pop();
				for (int j = 1; j <= n; ++j)
					if (Flag[u][j] && !color[j]){
						color[j] = num, type[j] = type[u] ^ 1;
						q.push(j);
					}
			}
		}
	for (int i = 1; i <= n; ++i)
		for (int j = 1; j <= n; ++j)
			if (i != j && color[i] == color[j] && type[i] == type[j] && Flag[i][j]) return puts("-1"), 0;
	for (int i = 1; i <= num; ++i){
		for (int j = 1; j <= n; ++j)
			if (color[j] == i && type[j]) a[i][1][++cnt[i][1]] = j; else
			if (color[j] == i && !type[j]) a[i][0][++cnt[i][0]] = j;
	}
	for (int i = 1; i < num; ++i)
		for (int j = 0; j <= 1; ++j)
			for (int k = 0; k <= 1; ++k)
				if (check(i, j, i + 1, k)) can[i][j][i + 1][k] = 1;
	ans = 1e9;
	dfs(2, cnt[1][0], cnt[1][1]);
	printf("%d\n", ans);
	return 0;
}