经典题，自己编的题面，不严谨。
题面
给一个带正权无向图（节点从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;
}