传送门
这道题，先用kruskal求一遍图中的最大生成树。
然后，倍增求lca，求lca的同时求出边权的最小值。
#include <cstring> #include <cstdio> #include <algorithm> int n, m, cnt, q, t, k; int f[10001], head[100001], p[10001][21], minn[10001][21], deep[10001]; bool vis[10001]; struct node tree[100001]; struct Node edge[100001]; inline void add(int a, int b, int c) inline int father(int a) inline bool cmp(node a, node b) void kruskal() if(k == n 1) break; } } void dfs(int i) } void init() } int lca(int a, int b) if(a == b) return ret; for(j = i; j >= 0; j) if(p[a][j] != p[b][j]) ret = std::min(ret, std::min(minn[a][0], minn[b][0])); return ret; } int main() init(); scanf("%d", &q); for(i = 1; i <= q; i++) return 0; }View Code
换了写法
惨啊，
i >= 0 我居然nc的用 i 代替
应该是 i >=1 用 i 代替
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 5 const int MAXN = 10001, MAXM = 50001, INF = 7074078; 6 int n, m, q, cnt, tot; 7 int head[MAXM], to[MAXM << 1], next[MAXM << 1], val[MAXM << 1]; 8 int f1[MAXN], f[MAXN][21], min[MAXN][21], deep[MAXN]; 9 10 struct node 11 p[MAXM]; 14 15 inline bool cmp(node a, node b) 16 19 20 inline void add(int x, int y, int z) 21 27 28 inline int find(int x) 29 32 33 inline int Min(int x, int y) 34 37 38 inline void swap(int &x, int &y) 39 42 43 inline void dfs(int u) 44 59 } 60 } 61 62 inline int lca(int x, int y) 79 80 int main() 81 102 if(tot == n 1) break; 103 } 104 for(i = 1; i <= n; i++) 105 if(!deep[i]) 106 dfs(i); 107 scanf("%d", &q); 108 for(i = 1; i <= q; i++) 109 114 return 0; 115 }View Code
上一篇：/和\的区别
下一篇：字典树 Trie树
最小生成树 lca 倍增
