首页 > 其他 > 详细

POJ 3692 Kindergarten(最大独立集)

时间:2017-02-15 16:13:30      阅读:227      评论:0      收藏:0      [点我收藏+]

 

【题目链接】 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(最大独立集)

原文:http://www.cnblogs.com/forever97/p/poj3692.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!