POJ2771最大独立集元素个数
元素 最大 个数 独立
2023-09-11 14:14:00 时间
题意:
女生和男生之间只要满足四个条件中的一个,那么两个人就不会在一起!然后给出一些男生和女生,问最多多少人一起做活动彼此不会产生暧昧关系。
思路:
这样的问题还是比较裸的问法,就是再问最大独立集元素个数,左边是男,右边是女,建立二分图,然后可能暧昧的连接在一起,最后n-最大匹配数,就行了,还有就是很多人都不是很理解这个结论为什么是对的,我说下我的简单理解,我们可以这样想,分成两个集合,这两个集合之间的最大暧昧关系我们只要删除产生暧昧关系的两个人其中的一个(这个不是随意删除谁,要看当时情况,但是肯定可以删除其中一个人)这样最后剩下的就没有办法在组成暧昧关系了,如果还不理解想想二分匹配匈牙利算法的过程,匹配完之后剩下的已经没有办法在匹配了,那么剩下的肯定是独立的,然后在在匹配里面选择一半拿出来(不是随意现则),可以有方法做到剩下的一半与之前匹配剩下的都是独立的,这样答案就是n-匹配数.
#include<stdio.h>
#include<string.h>
#define N_node 500 + 50
#define N_edge 500 * 500 + 50
typedef struct
{
int a;
char b[5];
char c[105];
char d[105];
}NODE;
typedef struct
{
int to ,next;
}STAR;
NODE node[N_node];
STAR E[N_edge];
int list[N_node] ,tot;
int mkdfs[N_node] ,mkgx[N_node];
void add(int a ,int b)
{
E[++tot].to = b;
E[tot].next = list[a];
list[a] = tot;
}
int DFS_XYL(int x)
{
for(int k = list[x] ;k ;k = E[k].next)
{
int to = E[k].to;
if(mkdfs[to]) continue;
mkdfs[to] = 1;
if(mkgx[to] == -1 || DFS_XYL(mkgx[to]))
{
mkgx[to] = x;
return 1;
}
}
return 0;
}
int abss(int x)
{
return x > 0 ? x : -x;
}
int main ()
{
int i ,j ,t ,n;
scanf("%d" ,&t);
while(t--)
{
scanf("%d" ,&n);
for(i = 1 ;i <= n ;i ++)
scanf("%d %s %s %s" ,&node[i].a ,node[i].b ,node[i].c ,node[i].d);
memset(list ,0 ,sizeof(list));
tot = 1;
for(i = 1 ;i <= n ;i ++)
{
if(node[i].b[0] != 'M') continue;
for(j = 1 ;j <= n ;j ++)
{
if(node[j].b[0] == 'M') continue;
if(abss(node[i].a - node[j].a) > 40) continue;
if(strcmp(node[i].c ,node[j].c)) continue;
if(!strcmp(node[i].d ,node[j].d)) continue;
add(i ,j);
}
}
memset(mkgx ,255 ,sizeof(mkgx));
int ans = 0;
for(i = 1 ;i <= n ;i ++)
{
memset(mkdfs ,0 ,sizeof(mkdfs));
ans += DFS_XYL(i);
}
printf("%d\n" ,n - ans);
}
return 0;
}
女生和男生之间只要满足四个条件中的一个,那么两个人就不会在一起!然后给出一些男生和女生,问最多多少人一起做活动彼此不会产生暧昧关系。
思路:
这样的问题还是比较裸的问法,就是再问最大独立集元素个数,左边是男,右边是女,建立二分图,然后可能暧昧的连接在一起,最后n-最大匹配数,就行了,还有就是很多人都不是很理解这个结论为什么是对的,我说下我的简单理解,我们可以这样想,分成两个集合,这两个集合之间的最大暧昧关系我们只要删除产生暧昧关系的两个人其中的一个(这个不是随意删除谁,要看当时情况,但是肯定可以删除其中一个人)这样最后剩下的就没有办法在组成暧昧关系了,如果还不理解想想二分匹配匈牙利算法的过程,匹配完之后剩下的已经没有办法在匹配了,那么剩下的肯定是独立的,然后在在匹配里面选择一半拿出来(不是随意现则),可以有方法做到剩下的一半与之前匹配剩下的都是独立的,这样答案就是n-匹配数.
#include<stdio.h>
#include<string.h>
#define N_node 500 + 50
#define N_edge 500 * 500 + 50
typedef struct
{
int a;
char b[5];
char c[105];
char d[105];
}NODE;
typedef struct
{
int to ,next;
}STAR;
NODE node[N_node];
STAR E[N_edge];
int list[N_node] ,tot;
int mkdfs[N_node] ,mkgx[N_node];
void add(int a ,int b)
{
E[++tot].to = b;
E[tot].next = list[a];
list[a] = tot;
}
int DFS_XYL(int x)
{
for(int k = list[x] ;k ;k = E[k].next)
{
int to = E[k].to;
if(mkdfs[to]) continue;
mkdfs[to] = 1;
if(mkgx[to] == -1 || DFS_XYL(mkgx[to]))
{
mkgx[to] = x;
return 1;
}
}
return 0;
}
int abss(int x)
{
return x > 0 ? x : -x;
}
int main ()
{
int i ,j ,t ,n;
scanf("%d" ,&t);
while(t--)
{
scanf("%d" ,&n);
for(i = 1 ;i <= n ;i ++)
scanf("%d %s %s %s" ,&node[i].a ,node[i].b ,node[i].c ,node[i].d);
memset(list ,0 ,sizeof(list));
tot = 1;
for(i = 1 ;i <= n ;i ++)
{
if(node[i].b[0] != 'M') continue;
for(j = 1 ;j <= n ;j ++)
{
if(node[j].b[0] == 'M') continue;
if(abss(node[i].a - node[j].a) > 40) continue;
if(strcmp(node[i].c ,node[j].c)) continue;
if(!strcmp(node[i].d ,node[j].d)) continue;
add(i ,j);
}
}
memset(mkgx ,255 ,sizeof(mkgx));
int ans = 0;
for(i = 1 ;i <= n ;i ++)
{
memset(mkdfs ,0 ,sizeof(mkdfs));
ans += DFS_XYL(i);
}
printf("%d\n" ,n - ans);
}
return 0;
}
相关文章
- jQuery操作DOM元素案例
- Java 第十一届 蓝桥杯 省模拟赛 最大的元素距离
- Java实现 LeetCode 381 O(1) 时间插入、删除和获取随机元素 - 允许重复
- 水平居中和transform: translateY(-50%) 实现元素垂直居中效果
- php数组中删除元素之重新索引
- Python简单遍历字典及删除元素的方法
- 【python cookbook】【数据结构与算法】4.找到最大或最小的N个元素
- C++ code:向量操作之添加元素
- 数组中的第K个最大元素
- 关于 Web Content-Security-Policy Directive 通过 meta 元素指定的一些测试用例
- 使用flex布局把三个元素分配成两列,第二列垂直布局两个元素
- ZZNUOJ_用C语言编写程序实现1137:查找最大元素(附完整源码)
- 2016. 增量元素之间的最大差值
- 增量元素之间的最大差值-c语言O(n)时间复杂度
- 习题 5.7 找出一个二维数组中的鞍点,即该位置上的元素在该行上最大,在该列上最小(也可能没有鞍点)。
- 输入10个数,求出最大元素是第几个数(数组作为函数參数)
- 【Web自动化总结】Selenium处理特殊页面元素技巧
- HTML5 ——《第二章—01》HTML5页面元素
- 【27】移除元素【LeetCode】
- C语言写元素类