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)


相关推荐

  • MJKDZ PS2手柄控制OskarBot小车(一):Arduino串口发送数据

    MJKDZ PS2手柄控制OskarBot小车(一):Arduino串口发送数据MJKDZPS2手柄控制OskarBot小车(一):Arduino串口发送数据【目录】    -1、无线通信模块设置        -1.1设置参数        -1.2调试步骤    -2、按键与通信格式        -2.1PS2按键定义        -2.2发送数据格式    -3、源代码        -3.1串口手…

  • STUN协议解释[通俗易懂]

    STUN协议解释[通俗易懂]最近工作中要用到stun,故学习了一下stun协议的知识。中文的文档没找到讲的比较好的,所以只能自己翻译了,官方文档太长就找了个谷歌排名第一的文章翻译一下。机翻+人翻,原文地址如下,在学习过程中还发现了原文作者的一个错误。。。应该是他错了。https://www.3cx.com/blog/voip-howto/stun-details/https://www.ietf.org/rfc/rf…

  • 计算机硬件知识

    一为何要学习计算机基础python是编程语言,即python是语言语言有英语、法语、葡萄牙语等,但凡是语言,都是用来沟通的介质。程序员编程的本质就是让计算机去工作,而编程语言就是程序员与计算机

  • CreateProcess和WinExec

    CreateProcess和WinExecCreateProcess非阻塞运行,而WinExec为阻塞运行,它非要等到返回时才继续执行。在两个进程共享同一个端口时,为了能让一个退出另一个申请,必须用函数CreateProcess,等到我的端口资源释放后,在运行另一个进程进行申请

  • html简单登录页面代码[通俗易懂]

    html简单登录页面代码[通俗易懂]图片必须是在Imges下的否则显示不出来(复制代码的话把图片换成你的图片就好了)代码如下&lt;html&gt;&lt;head&gt;&lt;title&gt;tes

  • 各大型邮箱smtp服务器及端口收集

    各大型邮箱smtp服务器及端口收集

发表回复

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

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