当前位置:网站首页>UVA 11080 – place the guards
UVA 11080 – place the guards
2022-07-07 21:04:00 【Full stack programmer webmaster】
Hello everyone , I meet you again , I'm the king of the whole stack .
UVA 11080 – Place the Guards
The question : Some cities . There are roads between them , Now we're going to place guards , The guard can watch the edge around the current point , There can only be one guard on one side , Ask if there is a plan , Suppose there are at least a few guards
Ideas : Bipartite graph decision , Record the number of white dots and black dots in the determination process , The small one is the number to be placed , Note that the assumption is 0, Then it should be plus 1
Code :
#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;}
Publisher : Full stack programmer stack length , Reprint please indicate the source :https://javaforall.cn/116454.html Link to the original text :https://javaforall.cn
边栏推荐
- 如何挑选基金产品?2022年7月份适合买什么基金?
- POJ 3140 Contestants Division「建议收藏」
- AADL Inspector 故障树安全分析模块
- Measure the height of the building
- CodeSonar通过创新型静态分析增强软件可靠性
- Cantata9.0 | new features
- [award publicity] issue 22 publicity of the award list in June 2022: Community star selection | Newcomer Award | blog synchronization | recommendation Award
- Deep learning model compression and acceleration technology (VII): mixed mode
- 【矩阵乘】【NOI 2012】【cogs963】随机数生成器
- uva 12230 – Crossing Rivers(概率)「建议收藏」
猜你喜欢
Details of C language integer and floating-point data storage in memory (including details of original code, inverse code, complement, size end storage, etc.)
OneSpin 360 DV新版发布,刷新FPGA形式化验证功能体验
ERROR: 1064 (42000): You have an error in your SQL syntax; check the manual that corresponds to your
CodeSonar网络研讨会
The latest version of codesonar has improved functional security and supports Misra, c++ parsing and visualization
MySQL storage expression error
智能软件分析平台Embold
Nebula Importer 数据导入实践
Measure the height of the building
AADL Inspector 故障树安全分析模块
随机推荐
ERROR: 1064 (42000): You have an error in your SQL syntax; check the manual that corresponds to your
【奖励公示】第22期 2022年6月奖励名单公示:社区明星评选 | 新人奖 | 博客同步 | 推荐奖
How to choose financial products? Novice doesn't know anything
不落人后!简单好用的低代码开发,快速搭建智慧管理信息系统
FatMouse&#39; Trade (Hangdian 1009)
easyui 日期控件清空值
Intelligent transportation is full of vitality. What will happen in the future? [easy to understand]
静态测试工具
Is private equity legal in China? Is it safe?
Write a jump table
国家正规的股票交易app有哪些?使用安不安全
智能软件分析平台Embold
恶魔奶爸 B1 听力最后壁垒,一鼓作气突破
[concept of network principle]
Mongodb learn from simple to deep
201215-03-19—cocos2dx内存管理–具体解释「建议收藏」
Spark judges that DF is empty
Codeforces 474 F. Ant colony
华泰证券可以做到万一佣金吗,万一开户安全嘛
单词反转实现「建议收藏」