HDU 1068 Girls and Boys(最大独立集合 = 顶点数 - 最大匹配数)
集合 and 最大 HDU 匹配 独立 顶点
2023-09-14 09:10:07 时间
HDU 1068 :题目链接
题意:一些男孩和女孩,给出一些人物关系,然后问能找到最多有多少个人都互不认识。
转换一下:就是大家都不认识的人,即最大独立集合
#include <iostream> #include <cstdio> #include <cstdlib> #include <cstring> #include <algorithm> #include <math.h> #define init(a) memset(a,0,sizeof(a)) #define PI acos(-1,0) using namespace std; const int maxn = 510; const int maxm = 100001; #define lson left, m, id<<1 #define rson m+1, right, id<<1|1 #define min(a,b) (a>b)?b:a #define max(a,b) (a>b)?a:b const int N = 50010; int ma[maxn][maxn]; int line[maxn]; bool vis[maxn]; int k,n,m; int DFS(int u) { // printf("u = %d\n",u); for(int v = 0;v<k;v++) { if(ma[u][v]== 1 && vis[v]==0) { vis[v] = 1; if(line[v]== -1 || DFS(line[v])) { line[v] = u; return 1; } } } return 0; } int K_M() { int ans = 0; memset(line,-1,sizeof(line)); for(int i = 0;i<k;i++) { init(vis); ans += DFS(i); } return ans; } int main() { int x,y; while(~scanf("%d",&k)) { init(ma); for(int j = 1;j<=k;j++) { scanf("%d: (%d)",&m,&n); for(int i = 1;i<=n;i++) { scanf("%d",&x); ma[m][x] = 1; } } //最大独立集合 = 顶点数 - 最大匹配数 int ans = K_M(); ans /= 2; printf("%d\n",k-ans); } return 0; }
相关文章
- APICloud Github 5大开源项目集合展示
- 谈谈集合.List
- (三)字典和集合
- python执行系统命令后获取返回值的几种方式集合
- 创建数组或项的集合
- 集合之Collection接口
- jQuery常用选择器【标签选择器】【id选择器】【class选择器】【集合选择器】
- 〖Python 数据库开发实战 - MongoDB篇⑪〗- MongoDB集合的增加操作
- python 不同集合上元素的迭代 chain()
- c# 变量,对象,静态类型,集合类的线程安全回顾
- 002-Python3-基础语法-赋值、显示类型、数据类型[数值、字符串、列表、元祖、集合、字典]
- 与各种表型或疾病相关的所有基因集合
- java集合: jdk1.8的hashMap源码简单理解
- 操作系统选择题集合(三)