HDu 2458(最大独立セット)

タイトルリンク:http://acm.hdu.edu.cn/showproblem.php?pid=2458
考え方:できるだけ多くの認識を持つ人を選ぶことを要求するため、私たちは逆に考えて、知らない女の子と男の子に縁を付けることができて、そこで問題は最大の独立集を求めることに転化します.
最大独立セット=頂点数-最大一致.

 1 #include<iostream>

 2 #include<cstdio>

 3 #include<cstring>

 4 #include<algorithm>

 5 #include<vector>

 6 using namespace std;

 7 #define MAXN 222

 8 vector<int>vet[MAXN];

 9 bool mark[MAXN];

10 bool map[MAXN][MAXN];

11 int ly[MAXN];

12 int G,B,m;

13 

14 int dfs(int u){

15    for(int i=0;i<vet[u].size();i++){

16       int v=vet[u][i];

17       if(!mark[v]){

18          mark[v]=true;

19          if(ly[v]==-1||dfs(ly[v])){

20             ly[v]=u;

21             return 1;

22          }

23       }

24    }

25    return 0;

26 }

27 

28 int MaxMatch(){

29    int res=0;

30    memset(ly,-1,sizeof(ly));

31    for(int i=1;i<=G;i++){

32       memset(mark,false,sizeof(mark));

33       res+=dfs(i);

34    }

35    return res;

36 }

37 

38 int main(){

39  //  freopen("1.txt","r",stdin);

40    int g,b,t=1;

41    while(scanf("%d%d%d",&G,&B,&m),(G+B+m)){

42       for(int i=1;i<=G;i++)vet[i].clear();

43       memset(map,false,sizeof(map));

44       for(int i=1;i<=m;i++){

45          scanf("%d%d",&g,&b);

46          map[g][b]=true;

47       }

48       for(int i=1;i<=G;i++){

49          for(int j=1;j<=B;j++){

50             if(!map[i][j]){

51                vet[i].push_back(j);

52             }

53          }

54       }

55       int ans=MaxMatch();

56       printf("Case %d: %d
",t++,G+B-ans);

57    }

58    return 0;

59 }

View Code