acwing::acwing861 命名空间参考

1. 二分图的最大匹配

更多...

函数
bool	find (vector< unordered_set< int > > &g, int x, vector< bool > &st, vector< int > &match)
int	main (istream &cin, ostream &cout)
	TEST (acwing859, case1)

详细描述

1. 二分图的最大匹配

函数说明

find()

bool acwing::acwing861::find	(	vector< unordered_set< int > > &	g,
		int	x,
		vector< bool > &	st,
		vector< int > &	match )

在文件 acwing.cpp 第 7522 行定义.

                                                                                              {
            for(const auto y: g[x]) {
                if(!st[y]) {
                    st[y] = true;
                    if(match[y] == 0 || find(g, match[y], st, match)) {
                        match[y] = x;
                        return true;
                    }
                }
            }
            return false;
        }

引用了 find().

被这些函数引用 find() , 以及 main().

main()

int acwing::acwing861::main	(	istream &	cin,
		ostream &	cout )

在文件 acwing.cpp 第 7497 行定义.

                                              {
            int n1;
            int n2;
            int m;
            cin >> n1 >> n2 >> m;
            int ans = 0;
            vector<unordered_set<int>> g(n1 + 1);
            vector match(n2 + 1, 0);
            vector st(n2 + 1, false);
            for(int i = 0; i < m; i++) {
                int u;
                int v;
                cin >> u >> v;
                g[u].insert(v);
            }
            for(int i = 1; i <= n1; i++) {
                st = vector(n2 + 1, false);
                if(find(g, i, st, match)) {
                    ans++;
                }
            }
            cout << ans;
            return 0;
        }

引用了 find().

被这些函数引用 TEST().

TEST()

acwing::acwing861::TEST	(	acwing859	,
		case1	)

在文件 acwing_test.cpp 第 3607 行定义.

                               {
            istringstream in("2 2 4\n"
                             "1 1\n"
                             "1 2\n"
                             "2 1\n"
                             "2 2");
            auto out = ostringstream();
            main(in, out);
            const auto ans = out.str();
            ASSERT_EQ("2", ans);
        }

引用了 main().