[HDU] 1068 Girls and Boys(二分图最大匹配)-白红宇

[HDU] 1068 Girls and Boys(二分图最大匹配)

阅读量：4514 次

发布时间：2019-06-08

本文共 823 字，大约阅读时间需要 2 分钟。

题目地址：

本题求二分图最大独立点集。因为最大独立点集=顶点数-最大匹配数。所以转化为求最大匹配。因为没有给出男女，所以每个人都用了两遍，所以结果应该除以2。

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 #include
          
            7 #include
           
             8 #include
            
              9 #include
             
              10 #include
              11 #include
               
                12 #include
                
                 13 #include
                 
                  14 using namespace std;15 #define clr(x,y) memset(x,y,sizeof(x))16 #define sqr(x) ((x)*(x))17 #define rep(i,a,b) for(int i=(a);i<=(b);i++)18 #define LL long long19 #define INF 0x3f3f3f3f20 #define A first21 #define B second22 #define PI 3.1415926535897932323 const int N=2000+131;24 int n,m,f[N],g[N][N],link[N];25 26 void init()27 {28 clr(f,0);29 clr(g,0);30 clr(link,-1);31 }32 33 bool find(int x)34 {35 for(int i=0;i