acwing::acwing858_408 命名空间参考

1. Prim算法求最小生成树

更多...

类
struct	pair_equal
struct	pair_hash
struct	tuple_compare

函数
int	main (istream &cin, ostream &cout)
	TEST (acwing858_408, case1)

详细描述

1. Prim算法求最小生成树

函数说明

main()

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

在文件 acwing408.cpp 第 712 行定义.

                                              {
            int n, m;
            int ans = 0;
            unordered_set<int> mst;
            unordered_map<int, unordered_set<pair<int, int>, pair_hash, pair_equal>> g;
            priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, tuple_compare> pq;
            cin >> n >> m;
            while(m--) {
                int u, v, w;
                cin >> u >> v >> w;
                if(g.find(u) == g.end()) {
                    g[u] = unordered_set<pair<int, int>, pair_hash, pair_equal>();
                }
                g[u].insert(make_pair(v, w));
                if(g.find(v) == g.end()) {
                    g[v] = unordered_set<pair<int, int>, pair_hash, pair_equal>();
                }
                g[v].insert(make_pair(u, w));
            }
            mst.insert(g.begin()->first);
            for(const auto &p: g[g.begin()->first]) {
                pq.push(make_tuple(g.begin()->first, p.first, p.second));
            }
            while(!pq.empty()) {
                auto [u, v, w] = pq.top();
                pq.pop();
                bool u_in = mst.find(u) != mst.end();
                bool v_in = mst.find(v) != mst.end();
                if(u_in && v_in)
                    continue;
                int to_insert = u_in ? v : u;
                mst.insert(to_insert);
                ans += w;
                for(const auto &p: g[to_insert]) {
                    if(mst.find(p.first) != mst.end() && mst.find(to_insert) != mst.end())
                        continue;
                    pq.push(make_tuple(to_insert, p.first, p.second));
                }
            }
            if(mst.size() == n) {
                cout << ans;
            } else {
                cout << "impossible";
            }
            return 0;
        }

被这些函数引用 TEST().

TEST()

acwing::acwing858_408::TEST	(	acwing858_408	,
		case1
	)

在文件 acwing408_test.cpp 第 1132 行定义.

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

引用了 main().