poj 3041 Asteroids (二分图)

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 #include<vector>
 5 using namespace std;
 6 #define N 555
 7 int map[N][N];
 8 int from[N],v[N],n;
 9 bool dfs(int x)
10 {
11     for (int i=1;i<=n;i++)
12     {
13         if (v[i]||!map[x][i]) continue;
14         v[i]=1;
15         if (from[i]==-1||dfs(from[i]))
16         {
17             from[i]=x;
18             return true;
19         }
20     }
21     return false;
22 }
23 int main()
24 {
25     int k,i,a,b,ans=0;
26     scanf("%d%d",&n,&k);
27     memset(map,0,sizeof(map));
28     while (k--)
29     {
30         scanf("%d%d",&a,&b);
31         map[a][b]=1;
32     }
33     memset(from,-1,sizeof(from));
34     for (i=1;i<=n;i++)
35     {
36         memset(v,0,sizeof(v));
37         ans+=dfs(i);
38     }
39     printf("%d\n",ans);
40 }