【题解】10.31模拟赛T2:蓝精灵的请求
程序员文章站
2022-06-02 12:49:18
...
我的做法是乱搞,跟std完全不一样
首先如果两个点之间没有边,那么这两个点肯定属于不同的点集
可以处理肯定属于同一点集的点
然后处理出一些点集,整体思想点集之间如果可以合并成同一个点集就连一条边
跑暴力求得答案
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;
}
上一篇: 怎样减肚子上的赘肉 坚持做这些动作
下一篇: 九方法减肚子最有效 清晨多喝白开水