12.25最小生成树（p,k复习）

初始时所有点都是蓝点，min[1]=0,min[2、3、4、5]=∞。权值之和MST=0。

第一次循环自然是找到min[1]=0最小的蓝点1。将1变为白点，接着枚举与1相连的所有蓝点2、3、4，修改它们与白点相连的最小边权。

最后权值之和MST=6。这n次循环，每次循环我们都能让一个新的点加入生成树，n次循环就能把所有点囊括到其中；每次循环我们都能让一条新的边加入生成树，n-1次循环就能生成一棵含有n个点的树；每次循环我们都取一条最小的边加入生成树，n-1次循环结束后，我们得到的就是一棵最小的生成树。这就是Prim采取贪心法生成一棵最小生成树的原理。算法时间复杂度：O (N2)。
?

P

注意几个问题，构成最小生成树的图一定是无向图，所以加边时要加两次

而且，边的最大量应设置为两倍的边数限制

#include<iostream>
#include<queue>
#include<set>
#include<vector>
using namespace std;
const int maxn = 5005;
const int maxm = 4e5 + 5;
const int inf = 1e9;
int cnt = 0, n, m, ans = 0, dis[maxn], head[maxn];
bool vis[maxn];
struct edge {
	int w, v, next;
}e[maxm];
void add(int u, int v, int w) {
	e[++cnt].v = v;
	e[cnt].w = w;
	e[cnt].next = head[u];
	head[u] = cnt;
}
void prim() {
	dis[1] = 0;
	vis[1] = 1;
	for (int i = head[1]; i; i = e[i].next) {
		dis[e[i].v] = min(dis[e[i].v], e[i].w);
	}
	for (int i = 1; i <= n - 1; i++) {
		int mind = inf, u;
		for (int j = 2; j <= n; j++) {//而如果加了vis限制后，后续的点就不会再次访问这个边，所以就不会再更新dis，从而使dis保持为延申时的最小代价
			if (!vis[j] && dis[j] <= mind) {//随着后面节点的不断更新，通向这个节点的路径都会被访问到，所以dis数组里保存的就是这个点边权的最小值
				u = j;//即只是在部分（已有可达的）路径中保存了一个最小路径dis,而不是通往这个节点的所有路径的最小路径
				mind = dis[j];//因为会出现这种情况，是初始向外延申，或者说后面的树要联通这个点时，路径是受限的
			}//如果要有意义，应该保证在更新dis数组时，不更新已确定的dis，
		}//所以dis数组保存的并不一定是边权，最后的dis数组应该是没意义的
		vis[u] = 1;//即此时联通图里各个点到这个点的距离，然后dis里保存的就是其中的最小代价
		ans += dis[u];//迭代中，每次联通的就是未访问过的点，而且是联通到这个点的最小代价，因为已经遍历了这个点到此时联通图里的所有代价
		for (int j = head[u]; j; j = e[j].next) {
			if(!vis[e[j].v])dis[e[j].v] = min(dis[e[j].v], e[j].w);//不用担心会再连到已确定的点上
		}//因为是树，每次都是连到新节点上，因为如果可以与已确定的点相连，且代价更小的话
	}//对于已确定的点而言，到这个点也是联通的
}
int main() {
	cin >> n >> m;
	for (int i = 1; i <= m; i++) {
		int u, v, w;
		cin >> u >> v >> w;
		add(u, v, w);
		add(v, u, w);
	}
	for (int i = 1; i <= n; i++)dis[i] = inf;
	prim();
	if (ans >= inf)cout << "orz";
	else cout << ans;
	return 0;
}

?K

Kruskal算法将一个连通块当做一个集合。Kruskal首先将所有的边按从小到大顺序排序（一般使用快排），并认为每一个点都是孤立的，分属于n个独立的集合。然后按顺序枚举每一条边。如果这条边连接着两个不同的集合，那么就把这条边加入最小生成树，这两个不同的集合就合并成了一个集合；如果这条边连接的两个点属于同一集合，就跳过。直到选取了n-1条边为止。

k算法就是通过并查集来检查这个边联通的两个部分是不是联通的，只有连接不连通的边才会被加入，不然，对于已经联通的，前面就已经有了更小的代价

生成树中没有边
Kruskal每次都选择一条最小的边，而且这条边的两个顶点分属于两个不同的集合。将选取的这条边加入最小生成树，并且合并集合。
第一次选择的是<1,2>这条边，将这条边加入到生成树中，并且将它的两个顶点1、2合并成一个集合。

#include<iostream>
#include<queue>
#include<set>
#include<vector>
#include<algorithm>
using namespace std;
const int maxn = 5005;
const int maxm = 2e5 + 5;
int cnt = 0, ce = 0, n, m, ans = 0, f[maxn];
struct edge {
	int w, v, u;
}e[maxm];
int find(int x) {
	if (f[x] == x)return x;
	else {
		f[x] = find(f[x]);
		return f[x];
	}
}
bool cmp(edge a, edge b) {
	return a.w < b.w;
}
int main() {
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		cin >> e[i].u >> e[i].v >> e[i].w;
	}
	for (int i = 1; i <= n; i++) {
		f[i] = i;
	}
	sort(e , e + m , cmp);//不用两倍，因为边是联通起点和终点，所以就查终点和起点即可
	for (int i = 0; i < m; i++) {
		if (find(e[i].u) == find(e[i].v))continue;
		f[find(e[i].u)] = e[i].v;
		ans += e[i].w;
		ce++;
		if (ce == n - 1)break;
	}
	if (ce < n - 1)cout << "orz";
	else cout << ans;
	return 0;
}

? ? 这里需要注意是? ? f[find(e[i].u)] = e[i].v;

而不是? f[e[i].u] = e[i].v;

因为下面那行相当于把一个孤点并到了另一个连通分量上，实际上并没有把两个连通图联通，只是从一个联通图里拿了一个点放到了另一个联通图里，而如果把一个联通图的爹放到了另一个联通图里，才是真正把两个联通图联通了，即? f[find(e[i].u)] = e[i].v;

流网络