还是畅通工程(最小生成树并查集 Prim Kruskal)

Description

某省调查乡村交通状况，得到的统计表中列出了任意两村庄间的距离。省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通（但不一定有直接的公路相连，只要能间接通过公路可达即可），并要求铺设的公路总长度为最小。请计算最小的公路总长度。

Input

测试输入包含若干测试用例。每个测试用例的第1行给出村庄数目N ( < 100 )；随后的N(N-1)/2行对应村庄间的距离，每行给出一对正整数，分别是两个村庄的编号，以及此两村庄间的距离。为简单起见，村庄从1到N编号。

当N为0时，输入结束，该用例不被处理。

Output

对每个测试用例，在1行里输出最小的公路总长度。

Sample Input

Sample Output

3

5

#include <iostream>

#include <algorithm>

using namespace std;

struct Node

{

    int a;

    int b;

    int dis;

};

int father[101];

Node node[5100];

bool cmp(Node A, Node B)

{

    return A.dis < B.dis;

}

int Find(int t)

{

    int temp = t;

    while (temp != father[temp])

        temp = father[temp];

    return father[t] = temp;

}

int main()

{

    ios::sync_with_stdio(false);

    cin.tie(NULL);

    cout.tie(NULL);

    int n, m;

    while (cin >> n && n != 0)

    {

        for (int i = 1; i <= n; ++i)

            father[i] = i;

        m = n * (n - 1) / 2;

        for (int i = 0; i < m; ++i)

            cin >> node[i].a >> node[i].b >> node[i].dis;

        sort(node, node + m, cmp);

        int ans = 0, cnt = 0;

        for (int i = 0; i < m; ++i)

        {

            int a = Find(node[i].a);

            int b = Find(node[i].b);

            if (a != b)

            {

                ans += node[i].dis;

                cnt++;

                father[b] = a;

                if (cnt == n - 1)

                    break;

            }

        }

        cout << ans << endl;

    }

    return 0;

}

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

int arc[100][100];

int V[100];

int ans, n;

int ok()

{

	for (int i = 0; i < n; i++)

		if (V[i] == 0)

			return 1;

	return 0;

}

void solve()

{

	int shortPath[100];

	int t = 0, i, j, min;

	memset(shortPath, 0x7f, sizeof(shortPath));

	memset(V, 0, sizeof(V));

	ans = 0;

	while (ok())

	{

		V[t] = 1;

		for (i = 0; i < n; i++)

			if (arc[t][i] > 0 && V[i] == 0 && arc[t][i] < shortPath[i])

				shortPath[i] = arc[t][i];

		min = 0;

		for (i = 1; i < n; i++)

			if (shortPath[min] > shortPath[i] && shortPath[i] != 0)

				min = i;

		if (min != 0)

		{

			ans += shortPath[min];

			t = min;

			shortPath[min] = 0;

		}

	}

}

int main()

{

	int m, i;

	int v1, v2, w;

	while (~scanf("%d", &n) && n)

	{

		memset(arc, 0, sizeof(arc));

		m = n * (n - 1) / 2;

		while(m--)

		{

			scanf("%d%d%d", &v1, &v2, &w);

			arc[v1 - 1][v2 - 1] = w;

			arc[v2 - 1][v1 - 1] = w;

		}

		solve();

		printf("%d\n", ans);

	}

	return 0;

}

巴特西

还是畅通工程(最小生成树并查集 Prim Kruskal)

Description

Input

Output

Sample Input

Sample Output

最新文章

热门文章

巴特西

还是畅通工程(最小生成树 并查集 Prim Kruskal)

Description

Input

Output

Sample Input

Sample Output

最新文章

热门文章

还是畅通工程(最小生成树并查集 Prim Kruskal)