最小生成树(1)

假装是prim算法(空间复杂度爆炸)

经典题,自己编的题面,不严谨。

题面

给一个带正权无向图(节点从1开始编号),求该带权无向图根节点为1的最小生成树。

(树是建出来了,但这个输出方法我并没有固定。。。到时候可能要sort一下之类的,临机应变吧)

题解如下,自己实现的垃圾prim算法,空间复杂度爆炸:

#include <cstdio>
#include <iostream>
#include <vector>
#define MAXN 1000
#define INFI 10000000
using namespace std;
/*
5 6
1 3 3
3 2 5
1 4 2
1 5 4
4 5 7
2 5 1

    4
  /
1 - 3
  \
    5 - 2
*/
struct relation
{
    int end;
    int weight;
};
vector<relation> node[MAXN];
vector<relation> tree[MAXN];
int noden, reln;
bool vis[MAXN];
void prim()
{
    vector<int> v;
    v.push_back(1);
    vis[1] = true;
    for (int i = 1; i < noden; i++)
    {
        int MIN = INFI;
        int MINJ = 0;
        int MINK = 0;
        for (int j = 0; j < v.size(); j++)
        {
            for (int k = 0; k < node[v[j]].size(); k++)
            {
                if (!vis[node[v[j]][k].end] && MIN > node[v[j]][k].weight)
                {
                    MIN = node[v[j]][k].weight;
                    MINJ = v[j];
                    MINK = node[v[j]][k].end;
                }
            }
        }
        if (MIN < INFI)
        {
            relation r;
            r.end = MINK;
            r.weight = MIN;
            tree[MINJ].push_back(r);
            vis[MINK] = true;
            v.push_back(MINK);
            // r.end = MINJ;
            // tree[MINK].push_back(r);
            // 要不要双向呢。。。反正是树,应当是不要双向的
        }
        else
        {
            return;
        }
    }
}
int main()
{
    cin >> noden >> reln;
    for (int i = 0; i < reln; i++)
    {
        int a, b;
        int weight;
        cin >> a >> b >> weight;
        relation r;
        r.end = b;
        r.weight = weight;
        node[a].push_back(r);
        r.end = a;
        node[b].push_back(r);
    }
    prim();
    for (int i = 1; i <= noden; i++)
    {
        for (int j = 0; j < tree[i].size(); j++)
        {
            cout << i << "->" << tree[i][j].end << endl;
        }
    }
    return 0;
}
Subscribe
提醒
guest
0 评论
Inline Feedbacks
View all comments