博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
hdu 2768(最大独立集)
阅读量:6150 次
发布时间:2019-06-21

本文共 591 字,大约阅读时间需要 1 分钟。

题目链接:

思路:把喜欢cat的和喜欢dog的看成两个集合,如果这两个集合有冲突,即cat.love==dog.hate或者cat.hate==dog.love,这连边,代表有矛盾,那么最后的结果不就是求一下最大独立集吗。

最大独立集=顶点数-最大匹配。

1 #include
2 #include
3 #include
4 #include
5 #include
6 using namespace std; 7 #define MAXN 2222 8 struct Node { 9 string love;10 string hate;11 } cat[MAXN],dog[MAXN];12 int cat_cnt,dog_cnt;13 bool map[MAXN][MAXN];14 bool mark[MAXN];15 int ly[MAXN];16 char s1[11],s2[11];17 18 int dfs(int u) {19 for(int v=0; v
View Code

 

转载地址:http://zagya.baihongyu.com/

你可能感兴趣的文章
Windows 8 开发之设置合约
查看>>
闲说HeartBeat心跳包和TCP协议的KeepAlive机制
查看>>
MoSQL
查看>>
Hibernate多对一外键单向关联(Annotation配置)
查看>>
《CLR via C#》读书笔记 之 方法
查看>>
设计模式:组合模式(Composite Pattern)
查看>>
ContentValues 和HashTable区别
查看>>
LogicalDOC 6.6.2 发布,文档管理系统
查看>>
给PowerShell脚本传递参数
查看>>
实战2——Hadoop的日志分析
查看>>
利用FIFO进行文件拷贝一例
查看>>
Ecshop安装过程中的的问题:cls_image::gd_version()和不支持JPEG
查看>>
Windows IOCP模型与Linux EPOLL模块之比较-
查看>>
模板方法模式- 设计模式学习
查看>>
resmgr:cpu quantum等待事件
查看>>
[原创]Nmap网络端口扫描工具介绍
查看>>
更改swing应用程序标题栏默认图标
查看>>
汇编跳转到c时,程序一开始设置栈指针
查看>>
How to get memcached all keys
查看>>
how to decompress gzip stream with zlib
查看>>