首页技术正文

POJ_1797 Heavy Transportation 【最大生成树的最小边】

程序员新良技术 2022年11月6日

0 收藏 426 点赞 669 浏览 1031 个字

一、题目

　POJ1797

二、分析

　题意就是让你找到从1到n的一条路，由于边的最大称重限制，你需要确定限制的最小值，也就是能运输的最大值。

　可以结合最小生成树想，利用并查集，然后不断更新答案即可，需要注意的是题意是1到n走到就可以了，并不需要走到每个点，所以不是完整的最大生成树，所以当1与n共父节点时直接返回结果即可。

三、AC代码

 1 #include <cstdio>
 2 #include <iostream>
 3 #include <algorithm>
 4 #include <cstring>
 5
 6 using namespace std;
 7 const int MAXN = 1e3 + 14;
 8
 9 struct edge
10 {
11     int from, to, cost;
12     bool operator < (const edge &e)
13     {
14         return cost > e.cost;
15     }
16 }E[MAXN*MAXN];
17 int m, n;
18 int par[MAXN];
19
20 int Find(int x)
21 {
22     return par[x] == x ? x : par[x] = Find(par[x]);
23 }
24
25 int Kruskal()
26 {
27     int Ans = 1e7;
28     for(int i = 1; i <= n; i++)
29         par[i] = i;
30     for(int i = 0; i < m; i++)
31     {
32         int a = E[i].from, b = E[i].to;
33         int fa = Find(a), fb = Find(b);
34         if(fa == fb)
35         {
36             continue;
37         }
38         else
39         {
40             Ans = min(Ans, E[i].cost);
41             par[fa] = fb;
42         }
43         if(Find(1) == Find(n))
44             return Ans;
45
46     }
47     return Ans;
48 }
49
50 int main()
51 {
52     //freopen("in.txt", "r", stdin);
53     int T, Case = 0;
54     scanf("%d", &T);
55     while(T--)
56     {
57         if(Case)
58             puts("");
59         scanf("%d%d", &n, &m);
60         for(int i = 0; i < m; i++)
61             scanf("%d%d%d", &E[i].from, &E[i].to, &E[i].cost);
62         sort(E, E + m);
63         printf("Scenario #%d:\n%d\n", ++Case, Kruskal());
64     }
65     return 0;
66 }