欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2022-06-02 12:49:18
...

【题解】10.31模拟赛T2:蓝精灵的请求
【题解】10.31模拟赛T2:蓝精灵的请求
我的做法是乱搞,跟std完全不一样
首先如果两个点之间没有边,那么这两个点肯定属于不同的点集
可以bfsbfs处理肯定属于同一点集的点
然后处理出一些点集,整体思想点集之间如果可以合并成同一个点集就连一条边
跑暴力dfsdfs求得答案

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;
}
相关标签: 题解