算法：最小生成树

prim

$bfs$的思想 割性质： 选择图中的一部分点作为$S$集合，该集合与剩余的$V-S$集合形成两部分。对于两部分之间不同权值的边，其中最小权值的边一定属于某个最小生成树的一部分。两部分之间划分的线可以理解为一条切割线。 通俗一点：以一个点为最小生成树起始点，将这个点与其它节点用一刀切割，取较小的权值，将这条边所连接的点加入最小生成树；继续划分，加入新的节点……

kruskal（敬请期待）

思路：

1. 将$cost$数组设为$inf$（题目要求最小）
2. 任选一个点作为最小生成树的起点，将它的$cost$设为$0$，并在队列内加入$cost$为0，节点编号为$1$的节点
3. 进行初始化：将最终答案设为$0$
4. 进行初始化：判断该节点是否在最小生成树内的数组（$little_tree$）设为$false$
5. 对图进行遍历 要点：
   • 判断当前节点是否存在于最小生成树内，如果存在，即时停止
   • 如果不存在，将状态设为存在，最终权值$ans$加上当前权值
   • 对图进行遍历，如果当前边的权值可以加入最小生成树将节点的$cost$设为$w$；无论能不能加入最小生成树，当前节点都需要入队

代码

# include <bits/stdc++.h>
# define int long long
# define endl '\n'
# define str string
# define pii pair < int , int >
# define fir first
# define sec second
# define fst ios::sync_with_stdio (0); cin.tie (0); cout.tie (0);

using namespace std;

const int N = 1e6 + 5, M = 2e6 + 5;
const int P = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const int LNF = 0x3f3f3f3f3f3f3f3f;

int n, m;

struct node {
	int v, w;
};

vector < node > mp[N];
int cost[N];
int little_tree[N];
int ans;

inline int prim () {
	priority_queue < pii , vector  < pii > , greater < pii > > q; // 进行优化 
	memset (cost, 0x3f, sizeof (cost));
	cost[1] = 0;
	q.push ({0, 1});
	while (! q.empty ()) {
		int u = q.top ().sec;
		int w = q.top ().fir;
		q.pop ();
		if (little_tree[u]) { // 说明当前节点已经在树里了 
			continue;
		}
		little_tree[u] = 1; // 新加入 
		ans += w;
		for (int i = 0; i < mp[u].size (); i ++ ) {
			int v = mp[u][i].v;
			int w = mp[u][i].w;
			if (! little_tree[v] && (w < cost[v])) {
				cost[v] = w;
			}
			q.push ({cost[v], v});
		}
	}
	return ans;
} 

signed main () {
//	fst;
//	freopen (".in", "r", stdin);
//	freopen (".out", "w", stdout);
	cin >> n >> m;
	for (int i = 1, u, v, w; i <= m; i ++ ) {
		cin >> u >> v >> w;
		mp[u].push_back ({v, w});
		mp[v].push_back ({u, w});
	}
	cout << prim ();
	return 0;
}