首页 > 代码库 > UVa 1395 (最小生成树) Slim Span

UVa 1395 (最小生成树) Slim Span

2024-10-22 20:20:02   209人阅读

题意：

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

分析：

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

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

技术分享
 1 #include <cstdio> 2 #include <vector> 3 #include <algorithm> 4 using namespace std; 5  6 const int INF = 1000000000; 7 const int maxn = 100 + 10; 8 int pa[maxn]; 9 10 int findset(int x) { return x == pa[x] ? x : pa[x] = findset(pa[x]); }11 12 struct Edge13 {14     int u, v, w;15     Edge(int u, int v, int w):u(u), v(v), w(w) {}16     bool operator < (const Edge& rhs) const17     {18         return w < rhs.w;19     }20 };21 22 vector<Edge> G;23 24 int main()25 {26     //freopen("in.txt", "r", stdin);27     int n, m;28     while(scanf("%d%d", &n, &m) == 2 && n)29     {30         G.clear();31         int u, v, w;32         for(int i = 0; i < m; ++i)33         {34             scanf("%d%d%d", &u, &v, &w);35             G.push_back(Edge(u, v, w));36         }37         sort(G.begin(), G.end());38         int ans = INF;39         for(int L = 0; L <= m - n + 1; ++L)40         {41             for(int i = 1; i <= n; ++i) pa[i] = i;42             int cnt = n;43             for(int R = L; R < m; ++R)44             {45                 int u = findset(G[R].u), v = findset(G[R].v);46                 if(u != v)47                 {48                     pa[u] = v;49                     if(--cnt == 1) { ans = min(ans, G[R].w - G[L].w); }50                 }51             }52         }53         if(ans == INF) ans = -1;54 55         printf("%d\n", ans);56     }57 58     return 0;59 }
代码君

 

UVa 1395 (最小生成树) Slim Span


联系
我们