根據(jù)二分圖的性質(zhì),最小結(jié)點(diǎn)覆蓋=結(jié)點(diǎn)數(shù)-最大匹配數(shù).
Code
1
#include <iostream>
2using namespace std;
3
4const int M = 121;
5int rlink[M];
6bool g[M][M];
7bool visited[M];
8
9int intersections, streets;
10
11bool Search(int pos)
12
{
13
for(int i = 1; i <= intersections; ++i)
14
{
15 if(!visited[i] && g[pos][i])
16 {
17 visited[i] = true;
18 if(rlink[i] == -1 || Search(rlink[i]))
19 {
20 rlink[i] = pos;
21 return true;
22
}
23 }
24 }
25
26 return false;
27
}
28
29int _tmain(int argc, _TCHAR* argv[])
30{
31 int cases;
32 cin >> cases;
33 while(cases--)
34 {
35 cin >> intersections >> streets;
36
37 memset(g, false, sizeof(g));
38 memset(rlink, -1, sizeof(rlink));
39
40 int start, end;
41 for(int i = 0; i < streets; ++i)
42 {
43 cin >> start >> end;
44 g[start][end] = true;
45 }
46
47 int result = 0;
48
49 for(int i = 1; i <= intersections; ++i)
50 {
51 memset(visited, false, sizeof(visited));
52
53 if(Search(i))
54 ++result;
55 }
56
57 cout << intersections - result << endl;
58 }
59 return 0;
60}
61
62posted on 2009-03-31 21:07
肖羽思 閱讀(616)
評(píng)論(1) 編輯 收藏 引用 所屬分類:
ZOJ