acwing::acwing858 命名空间参考

1. Prim算法求最小生成树

更多...

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

详细描述

1. Prim算法求最小生成树

函数说明

main()

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

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

                                              {
            unsigned n;
            unsigned m;
            cin >> n >> m;
            vector g(n + 1, vector(n + 1, INT_MAX));
            vector dist(n + 1, INT_MAX);
            for(unsigned i = 0; i < m; i++) {
                int u;
                int v;
                int w;
                cin >> u >> v >> w;
                w       = min(w, g[u][v]);
                w       = min(w, g[v][u]);
                g[u][v] = w;
                g[v][u] = w;
            }
            unordered_set<int> us;
            int ans = 0;
            for(int i = 0; i < n; i++) {
                int t = -1;
                for(int j = 1; j <= n; j++) {
                    if(!us.contains(j) && (t == -1 || dist[t] > dist[j])) {
                        t = j;
                    }
                }
                if(i > 0 && dist[t] == INT_MAX) {
                    cout << "impossible";
                    return 0;
                }
                if(i > 0) {
                    ans += dist[t];
                }
                for(int j = 1; j <= n; j++) {
                    dist[j] = min(dist[j], g[t][j]);
                }
                us.insert(t);
            }
            cout << ans;
            return 0;
        }

被这些函数引用 TEST().

TEST() [1/2]

acwing::acwing858::TEST	(	acwing858	,
		case1
	)

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

                               {
            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::acwing858::TEST	(	acwing858	,
		case2
	)

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

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

引用了 main().