二分匹配 匈牙利算法 模板-------------------C语言——菜鸟级

#include<string.h>
#include<stdio.h>
#define maxn 160
int a[maxn],b[maxn],c[maxn],d[maxn];
int used[maxn];
int girl[maxn],line[maxn][maxn];
int n;

int  Find(int x)
{ int j;
    for( j=1;j<=n;j++)
    { if(line[x][j]&&!used[j])
        { used[j]=1;
          if(girl[j]==0||Find(girl[j])){girl[j]=x;return 1;}
        }
    }
    return 0;}

int main()
{ int i,j;
    scanf("%d",&n);
    for( i=1;i<=n;i++) scanf("%d%d",&a[i],&b[i]);
    for( i=1;i<=n;i++) scanf("%d%d",&c[i],&d[i]);
    memset(line,0,sizeof(line));
    for( i=1;i<=n;i++)
    {
        for( j=1;j<=n;j++){
            if((a[i]<c[j])&&(b[i]<d[j])){
                line[i][j]=1;
            }
        }
    }
    memset(girl,0,sizeof(girl));
    int ans=0;
    for(i=1;i<=n;i++){
        memset(used,0,sizeof(used));
        if(Find(i)) ans++;
    }
   printf("%d\n",ans);
    return 0;
}
  

 

  
 
 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
  
39
  
40
  
41
 

文章来源: fivecc.blog.csdn.net，作者：Five-菜鸟级，版权归原作者所有，如需转载，请联系作者。

原文链接：fivecc.blog.csdn.net/article/details/80543442