洛谷P1330封锁阳光大学题解
2024-08-24 21:21:58
题意
此题可以说是一个很裸的一个二分图染色,但是比较不同的是,这个图中可能是不联通的,因此我们需要找到所有的联通块,然后一一选出每个联通块中黑块与白块中最小的个数,然后加入到最后的答案中去,也是很坑的一点。
然后就需要用到深搜来二分图染色,就是如果当前颜色为白色,那接下来所遍历到的点的颜色则一定要与当前颜色相反.
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <vector>
using namespace std;
const int maxn=10010;
int n,m,tot_1,tot_2,ans;
vector <int> e[1010];
int f[maxn];
void dfs(int u)
{
for(int i = 1; i < e[u].size(); i++)
{
if (f[u] == f[e[u][i]])
{
cout<<"Impossible";
exit(0);
}
if (!f[e[u][i]])
{
f[e[u][i]] = 3 - f[u];
if(f[e[u][i]] == 1)
tot_1++;
else
tot_2++;
dfs(e[u][i]);
}
}
}
int main()
{
int x, y;
cin >> n >> m;
for(int i = 1; i <= m; i++)
{
cin >> x >> y;
e[x].push_back(y);
e[y].push_back(x);;
}
for(int i = 1; i <= n; i++)
if(!f[i])
{
f[i] = 1;
tot_1 = 1;
tot_2 = 0;
dfs(i);
tot_1 = min(tot_1,tot_2);
ans += tot_1;
}
cout<<ans;
return 0;
}
最新文章
- 《Ansible权威指南》笔记(4)——Playbook
- php7.0.12 laravel 链接sqlserver数据库
- 一般html5 手机端头部需要
- mysql的ONLY_FULL_GROUP_BY语义 --转自http://www.wtoutiao.com/p/19dh3ec.html
- [AIR] 在 Adobe AIR 中为不同屏幕尺寸的多种设备提供支持
- 七周七语言——Prolog(二)
- Android 颜色渲染(五) LinearGradient线性渲染
- Android中的几种多线程实现
- 如何使用padlepadle 进行意图识别-开篇
- vue + element + 初始化项目
- ADT打开layout目录的xml报错java.lang.NullPointerException
- Qt信号槽第5个参数
- RSA 格式 - 转载
- IP白名单
- Java GC机制中Minor GC/Full GC
- 报错解决——-bash: wget: command not found
- Uni2D入门
- layer_mobile的简单使用
- 跨站点脚本编制-XSS 描述及解决方法
- Asp.net MVC中repository和service的区别