浙江省城乡与住房建设厅网站,佛山建设网站公司吗,广州市番禺区,腾讯微信公众号题意#xff1a;求一条路径#xff0c;使得这条边连接1到n#xff0c;求边权值的最大值与最小值的差 题解#xff1a;最小生成树#xff0c;对边权排序#xff0c;可以枚举边的最大和最小的值#xff0c;判断能否使得1和n连通 #include bits/stdc.h
#define ll …题意求一条路径使得这条边连接1到n求边权值的最大值与最小值的差 题解最小生成树对边权排序可以枚举边的最大和最小的值判断能否使得1和n连通 #include bits/stdc.h
#define ll long long
#define maxn 1010
using namespace std;
struct edge{ll from,to,weight;
};
int cmp(edge a,edge b){return a.weightb.weight;
}
vectoredgeedges;
int fa[maxn];
int find(int x){return xfa[x]?x:(fa[x] find(fa[x]));
}
void init(int n){for(int i1;in;i) fa[i] i;
}
int main(){ll n,m,i,j,a,b,c, ma -1e17,mi 1e17, ans 1e18;cinnm;for(i0;im;i){cinabc;edges.push_back((edge){a,b,c});}sort(edges.begin(), edges.end(), cmp);for(i0;im;i){init(n);mi 1e17;ma -1e18;for(ji;jm;j){edge e edges[j];mi min(e.weight, mi);ma max(e.weight, ma);int fau find(e.from);int fav find(e.to);if(fau ! fav) fa[fau] fav;if(find(n) find(1)) break;}if(jm) ans min(ans, ma-mi);}coutansendl;return 0;
} View Code 转载于:https://www.cnblogs.com/Noevon/p/7162632.html
