dfs

应用：求最小生成树某一结点到其它各节点的路径上的最大边

#include<iostream>
using namespace std;
const int N = 100;
int n, m;
bool vis[N][N]; int g[N][N]; 
struct edge{
	int u, v, d;
	inline void init(){
		u = v = 0;
		d = -1;
	}
}dp[N];
void dfs(int now, int last){
	for (int i = 2; i <= n; i++){
		if (last == i || !g[now][i]){
			continue;
		}
		if (dp[i].d == -1){
			if (dp[now].d > g[now][i]){
				dp[i] = dp[now];
			}
			else{
				dp[i].u = now;
				dp[i].v = i;
				dp[i].d = g[now][i];
			}
		}
		dfs(i, now);
	}
}
int main(){
	fill(g[0], g[0] + N*N, 0);
	cin >> n>>m;
	for (int i = 0; i < m; i++){
		int x, y, w;
		cin >> x >> y >> w;
		g[x][y] = g[y][x] = w;
	
	}
	for (int i = 1; i <= n; i++){
		dp[i].init();
	}
	dfs(1, -1);
	for (int i = 1; i <= n; i++){
		cout << "1到"<<i<<"的路径上的最大边为：" << dp[i].u << " " << dp[i].v << " " << dp[i].d << endl;
	}
	s...