hdu1068 Girls and Boys

墨蓝 2022-01-05 17:25 142阅读 0赞

题目：http://acm.hdu.edu.cn/showproblem.php?pid=1068

二分图的最大独立集数=节点数（n）— 最大匹配数（m）

另外需要注意的是：

本题求出的最大匹配数是实际的两倍需要m/2

1 #include<iostream>
     2 #include<stdio.h>
     3 #include<math.h>
     4 #include<string.h>
     5 #include<stdlib.h>
     6 using namespace std;
     7 const int N=510;
     8 int a[N][N];
     9 int match[N];
    10 int use[N];
    11 int n;
    12 int dfs(int u)
    13 {
    14     for(int i=0;i<n;i++)
    15     {
    16         if(a[u][i] && !use[i])
    17         {
    18             use[i]=1;
    19             if(match[i]==-1 || dfs(match[i]))
    20             {
    21                 match[i]=u;
    22                 return 1;
    23             }
    24         }
    25     }
    26     return 0;
    27 }
    28 int bipartite()
    29 {
    30     int res=0;
    31     memset(match,-1,sizeof(match));
    32     for(int i=0;i<n;i++)
    33     {
    34         memset(use,0,sizeof(use));
    35         if(dfs(i))
    36         res++;
    37     }
    38     return res;
    39 }
    40 int main()
    41 {
    42     //freopen("in.txt","r",stdin);
    43     while(~scanf("%d",&n))
    44     {
    45         int q,p,m;
    46         memset(a,0,sizeof(a));
    47         for(int i=0;i<n;i++)
    48         {
    49             scanf("%d: (%d) ",&q,&m);
    50             for(int j=0;j<m;j++)
    51             {
    52                 scanf("%d",&p);
    53                 a[q][p]=1;
    54             }
    55         }
    56         int x=n-bipartite()/2;
    57         printf("%d\n",x);
    58     }
    59     return 0;
    60 }

转载于:https://www.cnblogs.com/xuesen1995/p/4537329.html