Posted on 2008-04-14 23:02
superman 阅读(190)
评论(0) 编辑 收藏 引用 所属分类:
URAL
1 /* Accepted 0.39 1 200 KB */
2 #include <iostream>
3
4 using namespace std;
5
6 int n, m, match[1000];
7 bool map[1000][1000], visited[1000];
8
9 bool dfs(int p)
10 {
11 for(int i = 0; i < m; i++)
12 if(map[p][i] && visited[i] == false)
13 {
14 visited[i] = true;
15 if(match[i] == -1 || dfs(match[i]))
16 {
17 match[i] = p;
18 return true;
19 }
20 }
21 return false;
22 }
23
24 int main()
25 {
26 int s, t;
27 cin >> n >> m >> s;
28 while(cin >> s >> t)
29 {
30 s--, t--;
31 map[s][t] = true;
32 }
33
34 int cnt = 0;
35 memset(match, 0XFF, sizeof(match));
36 for(int i = 0; i < n; i++)
37 {
38 memset(visited, false, sizeof(visited));
39 cnt += dfs(i);
40 }
41
42 cout << n + m - 2 * cnt + cnt << endl;
43
44 return 0;
45 }
46