当前位置:网站首页>UVA 11080 – Place the Guards(二分图判定)
UVA 11080 – Place the Guards(二分图判定)
2022-07-07 18:44:00 【全栈程序员站长】
大家好,又见面了,我是全栈君。
UVA 11080 – Place the Guards
题意:一些城市。之间有道路相连,如今要安放警卫,警卫能看守到当前点周围的边,一条边仅仅能有一个警卫看守,问是否有方案,假设有最少放几个警卫
思路:二分图判定,判定过程记录下白点和黑点个数,小的就是要安放的个数,注意假设是0,那么应该是加1
代码:
#include <cstdio>#include <cstring>#include <vector>using namespace std;const int N = 205;int color[N];vector<int> g[N];int b, w;int bipartite(int u) { if (color[u] == 1) b++; if (color[u] == 2) w++; for (int i = 0; i < g[u].size(); i++) { int v = g[u][i]; if (color[u] == color[v]) return false; if (!color[v]) { color[v] = 3 - color[u]; if (!bipartite(v)) return false; } } return true;}int t, n, m;int solve() { int ans = 0; for (int i = 0; i < n; i++) { if (!color[i]) { color[i] = 1; b = w = 0; if (!bipartite(i)) return -1; ans += max(1, min(b, w)); } } return ans;}int main() { scanf("%d", &t); while (t--) { scanf("%d%d", &n, &m); for (int i = 0; i < n; i++) { g[i].clear(); color[i] = 0; } int u, v; while (m--) { scanf("%d%d", &u, &v); g[u].push_back(v); g[v].push_back(u); } printf("%d\n", solve()); } return 0;}
发布者:全栈程序员栈长,转载请注明出处:https://javaforall.cn/116454.html原文链接:https://javaforall.cn
边栏推荐
- 最新版本的CodeSonar改进了功能安全性,支持MISRA,C ++解析和可视化
- Ubuntu安装mysql8遇到的问题以及详细安装过程
- POJ 1742 Coins ( 单调队列解法 )「建议收藏」
- 论文解读(ValidUtil)《Rethinking the Setting of Semi-supervised Learning on Graphs》
- Helix QAC 2020.2新版静态测试工具,最大限度扩展了标准合规性的覆盖范围
- 微服务远程Debug,Nocalhost + Rainbond微服务开发第二弹
- CodeSonar网络研讨会
- How to choose financial products? Novice doesn't know anything
- 反诈困境,国有大行如何破局?
- Mrs offline data analysis: process OBS data through Flink job
猜你喜欢
How does codesonar help UAVs find software defects?
Network principle (1) - overview of basic principles
ERROR: 1064 (42000): You have an error in your SQL syntax; check the manual that corresponds to your
Cantata9.0 | 全 新 功 能
One click deployment of any version of redis
Intelligent software analysis platform embold
Small guide for rapid formation of manipulator (12): inverse kinematics analysis
解决使用uni-app MediaError MediaError ErrorCode -5
Jenkins 用户权限管理
Nebula importer data import practice
随机推荐
Measure the height of the building
【网络原理的概念】
开发一个小程序商城需要多少钱?
npm uninstall和rm直接删除的区别
Implement secondary index with Gaussian redis
Alibaba cloud award winning experience: how to mount NAS file system through ECS
ISO 26262 - 基于需求测试以外的考虑因素
Deep learning model compression and acceleration technology (VII): mixed mode
CodeSonar如何帮助无人机查找软件缺陷?
Make this crmeb single merchant wechat mall system popular, so easy to use!
解决使用uni-app MediaError MediaError ErrorCode -5
easyui 日期控件清空值
Tensorflow2. How to run under x 1 Code of X
如何满足医疗设备对安全性和保密性的双重需求?
如何挑选基金产品?2022年7月份适合买什么基金?
How to implement safety practice in software development stage
使用camunda做工作流设计,驳回操作
刚开户的能买什么股票呢?炒股账户安全吗
ERROR: 1064 (42000): You have an error in your SQL syntax; check the manual that corresponds to your
One click deployment of any version of redis