poj 1466 最大独立集
#include<stdio.h>
#include<string.h>//这个分开后男的站在一边女的站在一边，不肯能有les或者gay。最大独立集=n-最大匹配数
#define N 510
int map[N][N],n,mark[N],link[N];
int find(int u) {
int i;
for(i=0;i<=n;i++)
if(!mark[i]&&map[u][i]) {
mark[i]=1;
if(link[i]==-1||find(link[i])) {
link[i]=u;
return 1;
}
}
return 0;
}
int main() {
int i,j,k,s,num;
while(scanf("%d",&n)!=EOF) {
memset(map,0,sizeof(map));
for(i=1;i<=n;i++) {
scanf("%d: (%d)",&num,&s);
while(s--) {
scanf("%d",&j);
map[i][j]=1;
}
}
k=0;
memset(link,-1,sizeof(link));
for(i=0;i<=n;i++) {
memset(mark,0,sizeof(mark));
k+=find(i);
}
printf("%d\n",n-k/2);
}
return 0;
}
最新文章
- MesaSQLite数据库的简单使用方法
- 通过PHP自带的$_SERVER判断 手机访问网站自动跳转到手机版
- （转载）python2+selenium自动化测试系列（二）
- mongodb系列3 mongo mongoskin 连接以及连接数的问题进阶
- pyenv ipython jupyter
- JVM调优-关于jvm的一些基本概念
- Ping-Pong (Easy Version)（DFS）
- ASP.NET 经典60道面试题
- windows下搭建apache+php+mysql
- avalonjs1.5 入门教程
- DataTable转化为List
- k8s实践 - 如何优雅地给kong网关配置证书和插件。
- FineUI十周年纪念版即将发布（基于像素的响应式布局，独此一家）！
- AndroidStudio 快捷键（最实用的20个）（转）
- Mysql 了解changeBuffer 与 purge 调优
- pip freeze 命令迁移模块
- linux c使用socket进行http 通信，并接收任意大小的http响应（二）
- ElasticSearch权威指南学习（排序）
- 使用thinkphp框架实现Excel导入数据库
- Mysql（MyISAM和InnoDB）及Btree和索引优化