题意: 一个男生集合和一个女生集合, 给出两个集合之间一一对应的关系, 求出两个集合中最大独立集的点数.
思路: 在二分图中, 最大独立集的点数 = 顶点数 - 最大匹配数 / 2;
求二分图的最大匹配数需要用匈牙利算法 (主要思想是求: 增广路径, 增广路径的数目 = 最大匹配数).
参考文章: https://blog.csdn.NET/u011032846/article/details/38031825
最大独立集: https://blog.csdn.NET/Richard_for_OI/article/details/79520470
二分图的最大匹配问题: https://blog.csdn.NET/x_y_q_/article/details/51920683
想了好久, 还是看代码吧.
- #include<iostream>
- #include<cstdio>
- #include<cstring>
- using namespace std;
- const int maxn = 550;
- int n,mx[maxn],my[maxn],vis[maxn],e[maxn][maxn];
- int path(int i) //i 是结合 x 中的节点
- {
- int j;
- for(j=0;j<n;j++) // 就是集合 y 中的节点
- {
- if(e[i][j]&&!vis[j])
- {
- vis[j]=1;
- if(my[j]==-1||path(my[j])) // 节点未访问或者访问到取反后的节点, 两者都不符合, 则说明再也找不到增广路径, 结束.
- {
- // 取反
- my[j]=i;
- mx[i]=j;
- return 1;
- }
- }
- }
- return 0;
- }
- int hungry() // 匈牙利算法, 求最大匹配
- {
- int res=0;
- memset(mx,-1,sizeof(mx));
- memset(my,-1,sizeof(my));
- for(int i=0;i<n;i++)
- {
- if(mx[i]==-1)
- {
- memset(vis,0,sizeof(vis));
- res+=path(i);
- }
- }
- return res;
- }
- int main(void)
- {
- int a,b,m,i;
- while(~scanf("%d",&n))
- {
- memset(e,0,sizeof(e));
- for(i=0;i<n;i++)
- {
- scanf("%d: (%d)",&a,&m);
- while(m--)
- {
- scanf("%d",&b);
- e[a][b]=1;
- }
- }
- printf("%d\n",n-hungry()/2);
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2798004.html