UVA 11080 – Place the Guards(二分图判定)

UVA 11080 – Place the Guards(二分图判定)

大家好,又见面了,我是全栈君。

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;}

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/116454.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • 2013年上海交大学生论文致谢[通俗易懂]

    2013年上海交大学生论文致谢[通俗易懂]公元两千零七年,岁次丁亥,仲夏之月,联科论文乃告杀青。辞穷理微,未敢称凌云之作,镂心鸟迹,得不效相如之叹?于是凭窗抱膝,寄情遐思。忆吾弱冠之龄入交通大学,意气方遒。尔来春秋有八,于今毕业,年齿已趋而立。户牅之外,万物滋荣,景致阙如昨日,堂室之内,联科已有苍颜白发矣。文凭两纸霜鬓两行,黄粱一枕功名一场,此皆寻常人生,乏善可陈。然联科身发受之父母,道德受之母校,学问受之师长,育教之恩,虽陨首结草不能报

  • python 多进程和多线程_python 多线程 多进程

    python 多进程和多线程_python 多线程 多进程前言在Python中,计算密集型任务适用于多进程,IO密集型任务适用于多线程正常来讲,多线程要比多进程效率更高,因为进程间的切换需要的资源和开销更大,而线程相对更小,但是我们使用的Python大多

  • file指定路径_目标实现的策略与路径

    file指定路径_目标实现的策略与路径FileProvider路径配置策略的理解★FileProvider的使用在AndroidManifest.xml中&amp;lt;providerandroid:name=&quot;android.support.v4.content.FileProvider&quot;android:authorities=&quot;set_your……

    2022年10月25日
  • 真理的基本的属性是_thread和handler区别

    真理的基本的属性是_thread和handler区别原文地址:http://blog.csdn.net/luckeryin/article/details/5649144C#中,Thread类有一个IsBackground的属性.MSDN上对它的解释是:获取或设置一个值,该值指示某个线程是否为后台线程。个人感觉这样的解释等于没有解释..Net中的线程,可以分为后台线程和前台线程。后台线程与前台线程并没有本质的区别,它们之间唯一

    2022年10月16日
  • 初中python培训机构

    初中python培训机构都知道现在Python这门编程语言很火,那它究竟火到什么程度?可能互联网上铺天盖地的Python学习贴不够直观,求职平台上Python相关工资水涨船高,也离我们普通人太远,但——Python被纳入基础教育体系呢?浙江省八年级将新增Python编程课程风变编程得到最新消息,在2020年9月开始的新学期中,浙江省三年级到九年级信息技术课将同步替换新教材,而其中最大的变化是,八年级将新增Python课程内容。同时,新高一信息技术编程语言由VB替换为Python,大数据、人工智能、程序设计与算法按照教材规划

  • JAVA查询Oracle数据库集群连接字符串及其JDBC jar包选择.

    JAVA查询Oracle数据库集群连接字符串及其JDBC jar包选择.

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号