POJ1466 最大点权独立集
最大 独立
2023-09-11 14:13:59 时间
题意:
给你n个人,再给你每个人都喜欢哪些人,让你找到一个最大的集合数,要求这个集合里面任意两个人都不喜欢彼此。
思路:
直接就是在问最大点权独立集元素个数,没啥解释的一遍二分图就行了,输出 n - sum / 2,说下为什么有的最大点权独立集合除以2有的不除吧,这个没什么固定的,比如说这个题给的边一定是双向的,也就是说 1 喜欢 2, 到2的时候也会喜欢1 所以就多出来一倍,要除以二,不是什么最大点权独立集元素个数就是等于n - sum / 2,比如题目给的是单项的关系,就不用了,说这个的原因是记得以前学二分图的时候在网上看到有人说最大点权独立集元素个数是 n - sum / 2。只要理解了就不会22的记住了。说多了。。。
#include<stdio.h>
#include<string.h>
#define N_node 500 + 50
#define N_edge 250000 + 50
typedef struct
{
int to ,next;
}STAR;
STAR E[N_edge];
int list[N_node] ,tot;
int mk_dfs[N_node] ,mk_gx[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(mk_dfs[to]) continue;
mk_dfs[to] = 1;
if(mk_gx[to] == -1 || DFS_XYL(mk_gx[to]))
{
mk_gx[to] = x;
return 1;
}
}
return 0;
}
int main ()
{
int n ,a ,b ,i ,nn;
while(~scanf("%d" ,&n))
{
memset(list ,0 ,sizeof(list));
tot = 1;
for(i = 1 ;i <= n ;i ++)
{
scanf("%d: (%d) " ,&a ,&nn);
for(int j = 1 ;j <= nn ;j ++)
{
scanf("%d" ,&b);
add(a+ 1 ,b + 1);
}
}
int sum = 0;
memset(mk_gx ,255 ,sizeof(mk_gx));
for(i = 1 ;i <= n ;i ++)
{
memset(mk_dfs ,0 ,sizeof(mk_dfs));
sum += DFS_XYL(i);
}
printf("%d\n" ,n - sum / 2);
}
return 0;
}
相关文章
- POJ3692 最大点权独立集元素个数
- uva 11248 Frequency Hopping (最大流)
- 【UOJ#80】二分图最大权匹配(KM)
- 最大数值(不能使用比较运算符)
- hihoCoder #1122 : 二分图二•二分图最大匹配之匈牙利算法
- 求公司派对的最大快乐值
- UVa 1220 Party at Hali-Bula (树形DP,最大独立集)
- 最大匹配数,最小路径覆盖数,最大独立数,最小点覆盖数 定理总结
- 戴尔凭借新的独立软件提升开放网络标杆 最大程度增加客户的选择和能力
- 《最大子序列的分析》
- JS在页面限制checkbox最大复选数
- POJ - 1466 Girls and Boys 二分图+最大独立集
- [LeetCode] Maximum Product of Three Numbers 三个数字的最大乘积
- 先取AOL,再收雅虎,威瑞森成为美国互联网最大地主