NOIP2013D1T3货车运输（最大生成树+倍增lca）

传送门

这道题，先用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

上一篇：【模板】判断二分图

下一篇：毕业了！

---

lca 最小生成树 倍增