和UVA - 1395有点相似，都是求最大边权和最小边权的差值。不过这里的边数要多得多，枚举边权会超时。 所以这里用的方法是最小生成树建完之后开始添边，添一条边就会形成一个环，找到环中最小的边删除。
#include<iostream> #include<string> #include<cstdio> #include<set> #include<stack> #include<list> #include<vector> #include<queue> #include<algorithm> #include<cstring> #include<cmath> #include<fstream> using namespace std; typedef long long ll; //ifstream cin; const int maxn = 350,maxe = maxn * maxn,INF = 0x3f3f3f3f; int n,m; struct node{ int u,v,w; bool operator < (const node &a) const { return w < a.w; } }e[maxe]; vector<pair<int,int>> r[maxn]; int top[maxn]; int find(int x){ return x == top[x] ? x : top[x] = find(top[x]); } bool vis[maxn * maxn]; node path[maxn]; int cnt; bool find_path(int fa,int u,int ed){//dfs找环，路径存在path数组内 if (u == ed) return true; for(int i = 0;i < r[u].size();++i){ int v = r[u][i].first,w = r[u][i].second; if (v == fa) continue; path[cnt++] = {u,v,w}; if (find_path(u,v,ed)) return true; cnt--; } return false; } inline void add(node &a){ int u = a.u,v = a.v,w = a.w; r[u].push_back({v,w}); r[v].push_back({u,w}); } inline void del(node &a){ int u = a.u,v = a.v; for(vector<pair<int,int>>::iterator it = r[u].begin();it != r[u].end();++it){ if (it->first == v){ r[u].erase(it); break; } } for(vector<pair<int,int>>::iterator it = r[v].begin();it != r[v].end();++it){ if (it->first == u){ r[v].erase(it); break; } } } void update(int u,int fa,int &mx,int &mi){//遍历树更新ans for(int i = 0;i < r[u].size();++i){ int v = r[u][i].first,w = r[u][i].second; if (v == fa) continue; mi = min(mi,w); mx = max(mx,w); update(v,u,mx,mi); } } void kruskal(){ memset(vis,0,sizeof vis);//最小生成树 for(int i = 0;i < n;++i) top[i] = i; int sum = 1,ans = INF; for(int k = 0;k < m;++k){ int u = e[k].u,v = e[k].v; int fu = find(u),fv = find(v); if (fu != fv){ top[fu] = fv; add(e[k]); vis[k] = 1; sum++; } if (sum == n){ ans = e[k].w - e[0].w; break; } } for(int k = 0;k < m;++k){//加边更新ans if (vis[k]) continue; int u = e[k].u,v = e[k].v; int mx = 0,mi = INF; cnt = 0; find_path(u,u,v); sort(path,path + cnt); del(path[0]); add(e[k]); update(0,0,mx,mi); ans = min(ans,mx - mi); } printf("%d\n",ans); } void init(){ int a,b,c; memset(e,0,sizeof e); for(int i = 0;i < n;++i) r[i].clear(); for(int i = 0;i < m;++i){ cin >> a >> b >> c; e[i] = {a,b,c}; } sort(e,e + m); kruskal(); } int main(){ //cin.open("in.txt"); while(cin >> n && n){ cin >> m; init(); } }