poj3041(BinCover)

 1 #include <queue>
 2 #include <cstdio>
 3 #include <iostream>
 4 #include<vector>
 5 #include<string>
 6 #include <cstring>
 7 #include <algorithm>
 8 #define mem(a,b) memset(a,b,sizeof(a))
 9 using namespace std;
10 const int maxn=505;
11 int m,n,linked[maxn],vis[maxn];
12 struct node 
13 {
14     int nex,to;
15 }edge[10010];
16 int fir[10010],cnt;
17 void add_e(int a,int b)
18 {
19     edge[cnt].to=b;
20     edge[cnt].nex=fir[a];
21     fir[a]=cnt++;
22 }
23 bool dfs(int a)
24 {
25 
26     for(int i=fir[a];i!=-1;i=edge[i].nex)
27     {
28         int to=edge[i].to;
29         if(!vis[to])
30         {
31             vis[to]=1;
32             if(linked[to]==-1||dfs(linked[to]))
33             {
34                 linked[to]=a;
35                 return 1;
36             }
37         }
38     }
39     return 0;
40 }
41 int main()
42 {
43     scanf("%d%d",&n,&m);
44     memset(fir,-1,sizeof(fir));
45     memset(linked,-1,sizeof(linked));
46     for(int i=1;i<=m;i++)
47     {
48         int a,b;
49         scanf("%d%d",&a,&b);
50         add_e(a,b);
51     }
52     int ans=0;
53     for(int i=1;i<=n;i++)
54     {
55         mem(vis,0);
56         if(dfs(i))
57         ans++;
58     }
59     printf("%d
",ans );
60 }
View Code