acwing::acwing859 命名空间参考

1. Kruskal算法求最小生成树

更多...

类
struct	edge

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

详细描述

1. Kruskal算法求最小生成树

函数说明

main()

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

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

                                              {
            int n;
            int m;
            cin >> n >> m;
            int ans = 0;
            int cnt = 1;
            vector<edge> edges(m);
            for(int i = 0; i < m; i++) {
                int u;
                int v;
                int n;
                cin >> edges[i].u >> edges[i].v >> edges[i].w;
            }
            sort(edges.begin(), edges.end());
            UnionFind uf(n + 1);
            for(const auto &edge: edges) {
                if(!uf.same(edge.u, edge.v)) {
                    cnt++;
                    uf.unite(edge.u, edge.v);
                    ans += edge.w;
                }
            }
            if(cnt < n) {
                cout << "impossible";
            } else {
                cout << ans;
            }
            return 0;
        }

引用了 UnionFind::same(), acwing::acwing859::edge::u, UnionFind::unite(), acwing::acwing859::edge::v , 以及 acwing::acwing859::edge::w.

被这些函数引用 TEST().

TEST() [1/2]

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

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

                               {
            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().

TEST() [2/2]

acwing::acwing859::TEST	(	acwing859	,
		case2
	)

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

                               {
            istringstream in("10 20\n"
                             "2 5 -6\n"
                             "6 8 -9\n"
                             "2 1 9\n"
                             "10 8 2\n"
                             "3 4 -1\n"
                             "6 7 5\n"
                             "1 2 6\n"
                             "8 7 -5\n"
                             "3 2 10\n"
                             "10 10 9\n"
                             "4 3 -1\n"
                             "7 8 8\n"
                             "3 3 6\n"
                             "6 9 -4\n"
                             "1 2 -9\n"
                             "6 6 6\n"
                             "3 2 7\n"
                             "9 10 4\n"
                             "4 5 -3\n"
                             "8 9 2");
            auto out = ostringstream();
            main(in, out);
            const auto ans = out.str();
            ASSERT_EQ("impossible", ans);
        }

引用了 main().