首页 > 代码库 > POJ 3692 Kindergarten（最大独立集）
POJ 3692 Kindergarten（最大独立集）
【题目链接】 http://poj.org/problem?id=3692
【题目大意】
男生相互之间都认识，女生相互之间也都认识，
一些男生和一些女生相互之间也认识，求找出最多的人参加派对，
他们相互之间都认识
【题解】
我们建认识图的反图，将相互之间不认识的连线，
那么问题转化为求这个图的最大独立集，
最大独立集答案为总点数减去最大匹配。
【代码】
#include <cstdio> #include <cstring> using namespace std; const int MAXV=500; int n,G[MAXV][MAXV],use[MAXV],match[MAXV]; int g,b,m,x,y,cas=0;bool dfs(int x){ for(int i=1;i<=b;i++){ if(use[i]==0&&G[x][i]){ use[i]=1; int j=match[i]; if(j==-1||dfs(j)){ match[i]=x; return 1; } } }return 0; } int bipartite_matching(){ int count=0; memset(match,-1,sizeof(match)); for(int i=1;i<=g;i++){ for(int j=1;j<=b;j++)use[j]=0; if(dfs(i))count++; }return count; }void init(){ memset(G,1,sizeof(G)); for(int i=0;i<m;i++){ scanf("%d%d",&x,&y); G[x][y]=0; }}void solve(){ printf("%d\n",g+b-bipartite_matching());}int main(){ while(scanf("%d%d%d",&g,&b,&m),g||b||m){ printf("Case %d: ",++cas); init(); solve(); }return 0;}POJ 3692 Kindergarten（最大独立集）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。