UVa 1395 (最小生成树) Slim Span

时间:2021-10-22 04:10:54

题意:

规定一棵生成树的苗条度为:最大权值与最小权值之差。给出一个n个顶点m条边的图,求苗条度最小的生成树。

分析:

按照边的权值排序,枚举边集的连续区间[L, R]的左边界L,如果这些区间刚好满足一个生成树,则存在一个苗条度不超过W[R] - W[L]的生成树。

话说,代码中用了STL的vector,慢了很多。

 #include <cstdio>
#include <vector>
#include <algorithm>
using namespace std; const int INF = ;
const int maxn = + ;
int pa[maxn]; int findset(int x) { return x == pa[x] ? x : pa[x] = findset(pa[x]); } struct Edge
{
int u, v, w;
Edge(int u, int v, int w):u(u), v(v), w(w) {}
bool operator < (const Edge& rhs) const
{
return w < rhs.w;
}
}; vector<Edge> G; int main()
{
//freopen("in.txt", "r", stdin);
int n, m;
while(scanf("%d%d", &n, &m) == && n)
{
G.clear();
int u, v, w;
for(int i = ; i < m; ++i)
{
scanf("%d%d%d", &u, &v, &w);
G.push_back(Edge(u, v, w));
}
sort(G.begin(), G.end());
int ans = INF;
for(int L = ; L <= m - n + ; ++L)
{
for(int i = ; i <= n; ++i) pa[i] = i;
int cnt = n;
for(int R = L; R < m; ++R)
{
int u = findset(G[R].u), v = findset(G[R].v);
if(u != v)
{
pa[u] = v;
if(--cnt == ) { ans = min(ans, G[R].w - G[L].w); }
}
}
}
if(ans == INF) ans = -; printf("%d\n", ans);
} return ;
}

代码君