10.31模拟赛T2

问题就是把整个图分为两个完全图

首先建一个原图的补图，然后可以发现这个补图有许多独立的连通块。

对于每个连通块，进行黑白染色，就可以得到一些性质（针对补图）：

问题转化为将补图分为两组，每组中在补图中互不连边（在原图中就是两两连边，完全图）同一个连通块里面，两种颜色的点肯定分属于两组。加入何组与颜色无关，只要保证一个连通块中的点没有在一组里面就好了

用一个可行性dp解决这个问题，dp[i][j]表示前i个连通块，以j个点为一组可不可行

$$dp[i][j]|=dp[i-1][j-a[i][k]]$$

Code：

#include <iostream> #include <cstdio> #include <cstring> #include <cstdlib> #include <cctype> #include <algorithm> #define MAXN 1000 #define INF 999999999999 #define int long long using namespace std; bool vis[MAXN], f[MAXN][MAXN], flag = 0; int dp[MAXN][MAXN], color[MAXN], a[MAXN][3], n, m, cnt; inline int read () { register int s = 0, w = 1; register char ch = getchar (); while (! isdigit (ch)) {if (ch == '-') w = -1; ch = getchar ();} while (isdigit (ch)) {s = (s << 3) + (s << 1) + (ch ^ 48); ch = getchar ();} return s * w; } void DFS (int now, int k) { if (flag) return; a[cnt][k]++, vis[now] = 1, color[now] = k; for (register int i = 1; i <= n; i++) if (i != now && ! f[now][i]) { if (color[i] == color[now]) {flag = 1; return;} if (! color[i]) DFS (i, 3-k); } } signed main () { n = read (), m = read (); for (register int i = 1; i <= m; i++) { int u = read (), v = read (); f[u][v] = f[v][u] = 1; } for (register int i = 1; i <= n; i++) if (! vis[i]) cnt++, DFS (i, 1); if (flag) return puts ("-1"), 0; dp[0][0] = 1; for (register int i = 1; i <= cnt; i++) for (register int j = 0; j <= n; j++) { if (j >= a[i][1]) dp[i][j] |= dp[i - 1][j - a[i][1]]; if (j >= a[i][2]) dp[i][j] |= dp[i - 1][j - a[i][2]]; } int ans = INF; for (register int i = 0; i <= n; i++) if (dp[cnt][i]) ans = min (ans, i * (i - 1) / 2 + (n - i) * (n - i - 1) / 2); return printf ("%lld\n", ans), 0; }