最短路算法三

图论三
20240624
算法实用主义，用到再学
1. 大纲：
a. 最小生成树都是无向图
难在建图，不考原理，重点记思路（是骨头），自己复述一遍，不能死记代码血肉

类似最短路

prim（类似dijkstra除了更新距离一个是到起点，一个是到集合距离就是dmin）
朴素版：稠密图， m>>n
堆优化：稀疏图少用，多用kruskal
kruskal：稀疏图 l时间花在排序上，m<n2，mlogm和mlogn一样的，
b. 二分图
c. 最大流算法：不考，竞赛题考
在这里插入图片描述

最小生成树（没有环，正负权都行！！！）的工程意义：
去环
铺路
已知n个城市的坐标，他们之间普电缆，允许相交，是城市之间相互连通
问dmin多少
就是给一个完全无向图，求距离总和min

不是欧拉图：一笔画到底

在这里插入图片描述

	注意for循环范围
	#include <cstring>
	#include<iostream>
	#include <algorithm>
	
	using namespace std;
	
	const int N = 510; //稠密图 邻接矩阵存
	const int INF = 0x3f3f3f3f;
	
	int n,m; 
	int g[N][N]; //邻接矩阵存图, 存的是点之间的距离
	int dist[N]; //点的集合的距离
	bool st[N]; //判断在s集合里？？
	
	int  prim(){
	    // 1 初始化dist
	    memset(dist, 0x3f, sizeof dist);
	    
	    int res= 0; //最小生成树所有边的长度之和
	    // 找t； 更新距离；加入s
	    for(int i = 0; i < n; i ++){
	        int t = -1; //t节点编号，除了第一个，后面不可能-1
	        for (int j  =1; j <= n; j ++){
	            // 这里为什么是1-n
	            
	            // 在集合外 &&（t=-1代表当前没找到任何一个点）
	            if(!st[j] && (t == -1 || dist[t] >dist[j]))
	                t = j;
	            // cout << t <<' '<< dist[t] << endl; //debug
	        }
	        
	        
	        // if(i)代表如果不是第一个点i =0（第一个距离默认是INF，不要判断） 
	        // 不是第一个点且，当前距离最近是INF，  说明不连通
	        if(i && dist[t] == INF) return INF;
	        
	        
	        // 这不能放在下面for后面，因为存在自环，先更新会导致dist[j] = 0 for循环里t不能是j
	        // 只要不是第一个点， dist[t] 是t与生成树（集合里每一个点的） 的边min的长度
	        if(i) res += dist[t];
	        
	        // 更新到集合距离 就这里和dijkstra不一样!!!
	        for(int j = 1; j <=n;  j++) dist[j] =min(dist[j], g[t][j]);
	        
	        
	        st[t]= true;  //下标容易写错i
	        
	    }
	    return res;
	}
	
	int main(){
	    scanf("%d%d", &n, &m);
	    
	    memset(g, 0x3f, sizeof g); //点之间初始化∞，不是dist
	    
	    
	    // 读边
	    while(m --){
	        int a, b, c;
	        scanf("%d%d%d",&a, &b, &c);
	        
	        g[a][b] = g[b][a] = min(g[a][b], c); //无向图， 重边取min
	    }
	    
	    int t = prim();
	    
	    // 所有点不连通，不存在生成树
	    if(t == INF) puts("impossible");
	    else printf("%d\n",t);
	    
	    return 0;
	}