首页 > 代码库 > BZOJ1977 [BeiJing2010组队]次小生成树 Tree
BZOJ1977 [BeiJing2010组队]次小生成树 Tree
恩，归类上来讲的话。。。是一道非常好的noip题。。。只不过嘛、、、（此处省略100字）
然后将如何做：
首先Kruskal求出最小生成树。
我们其实可以发现严格的次小生成树不可能在MST上改两条边 <=> 只能改一条边。
那么如何改呢？
每次在MST中加入一条非树边，即不在MST的边，那么会形成一个环，只要找到换上的严格小于当前边权的最大值，删之，就形成了次小生成树的候选。
由Kruskal的算法保证加入的边权一定是环上最大的，因此我们要记录树链上的最大值和次大值（因为是严格小于）
而记录的方法就是倍增。。。noip难度。。。T T
对每条非树边都做一次即可。
复杂度大概是O(m * logm + n * logn + (m - n) * logn)
1 /************************************************************** 2 Problem: 1977 3 User: rausen 4 Language: C++ 5 Result: Accepted 6 Time:1740 ms 7 Memory:32628 kb 8 ****************************************************************/ 9 10 #include <cstdio> 11 #include <algorithm> 12 13 using namespace std; 14 typedef long long ll; 15 const int N = 100001; 16 const int M = 300001; 17 struct data{ 18 int x, y, v; 19 bool selected; 20 }a[M]; 21 struct edge{ 22 int next, to ,v; 23 }e[N * 2]; 24 struct tree_node{ 25 int dep, fa[17], d1[17], d2[17]; 26 }tr[N]; 27 inline bool operator < (const data a, const data b){ 28 return a.v < b.v; 29 } 30 31 int n, m, cnt, tot, del = 1e9; 32 int first[N], fa[N]; 33 ll ans; 34 35 inline int read(){ 36 int x = 0, sgn = 1; 37 char ch = getchar(); 38 while (ch < ‘0‘ || ch > ‘9‘){ 39 if (ch == ‘-‘) sgn = -1; 40 ch = getchar(); 41 } 42 while (ch >= ‘0‘ && ch <= ‘9‘){ 43 x = x * 10 + ch - ‘0‘; 44 ch = getchar(); 45 } 46 return sgn * x; 47 } 48 49 inline void add_edge(int x, int y, int z){ 50 e[++tot].next = first[x], first[x] = tot; 51 e[tot].to = y, e[tot].v = z; 52 } 53 54 void add_Edges(int X, int Y, int Z){ 55 add_edge(X, Y, Z); 56 add_edge(Y, X, Z); 57 } 58 59 int find_fa(int x){ 60 return x == fa[x] ? x : fa[x] = find_fa(fa[x]); 61 } 62 63 void dfs(int p){ 64 int i, x, y, FA; 65 for (i = 1; i <= 16; ++i){ 66 if (tr[p].dep < (1 << i)) break; 67 FA = tr[p].fa[i - 1]; 68 tr[p].fa[i] = tr[FA].fa[i - 1]; 69 tr[p].d1[i] = max(tr[p].d1[i - 1], tr[FA].d1[i - 1]); 70 if (tr[p].d1[i - 1] == tr[FA].d1[i - 1]) 71 tr[p].d2[i] = max(tr[p].d2[i - 1], tr[FA].d2[i - 1]); 72 else { 73 tr[p].d2[i] = min(tr[p].d1[i - 1], tr[FA].d1[i - 1]); 74 tr[p].d2[i] = max(tr[p].d2[i - 1], tr[p].d2[i]); 75 tr[p].d2[i] = max(tr[p].d2[i], tr[FA].d2[i - 1]); 76 } 77 } 78 for (x = first[p]; x; x = e[x].next) 79 if ((y = e[x].to) != tr[p].fa[0]){ 80 tr[y].fa[0] = p, tr[y].d1[0] = e[x].v, tr[y].dep = tr[p].dep + 1; 81 dfs(y); 82 } 83 } 84 85 inline int lca(int x, int y){ 86 if (tr[x].dep < tr[y].dep) swap(x, y); 87 int tmp = tr[x].dep - tr[y].dep, i; 88 for (i = 0; i <= 16; ++i) 89 if ((1 << i) & tmp) x = tr[x].fa[i]; 90 for (i = 16; i >= 0; --i) 91 if (tr[x].fa[i] != tr[y].fa[i]) 92 x = tr[x].fa[i], y = tr[y].fa[i]; 93 return x == y ? x : tr[x].fa[0]; 94 } 95 96 void calc(int x, int f, int v){ 97 int mx1 = 0, mx2 = 0, tmp = tr[x].dep - tr[f].dep, i; 98 for (i = 0; i <= 16; ++i) 99 if ((1 << i) & tmp){100 if (tr[x].d1[i] > mx1)101 mx2 = mx1, mx1 = tr[x].d1[i];102 mx2 = max(mx2, tr[x].d2[i]);103 x = tr[x].fa[i];104 }105 del = min(del, mx1 == v ? v - mx2 : v - mx1);106 }107 108 void work(int t, int v){109 int x = a[t].x, y = a[t].y, f = lca(x, y);110 calc(x, f, v);111 calc(y, f, v);112 }113 114 int main(){115 n = read(), m = read();116 int i, f1, f2, TOT = 0;117 for (i = 1; i <= m; ++i)118 a[i].x = read(), a[i].y = read(), a[i].v = read();119 for (i = 1; i <= n; ++i)120 fa[i] = i;121 sort(a + 1, a + m + 1);122 for (i = 1; i <= m; ++i)123 if ((f1 = find_fa(a[i].x)) != (f2 = find_fa(a[i].y))){124 fa[f1] = f2;125 ans += a[i].v;126 a[i].selected = 1;127 add_Edges(a[i].x, a[i].y, a[i].v);128 ++TOT;129 if (TOT == n - 1) break;130 }131 dfs(1);132 for (i = 1; i <= m; ++i)133 if (!a[i].selected)134 work(i, a[i].v);135 printf("%lld\n", ans + del);136 return 0;137 }
BZOJ1977 [BeiJing2010组队]次小生成树 Tree
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。