题目链接~~>
做题感悟:这题開始看到时感觉不是树不优点理,一想能够用 Kruskal 处理成树 ,然后就好攻克了。
解题思路:
先用 Kruskal 处理出最小生成树。然后用树链剖分 + 线段树处理就能够了。
代码:
- #include < iostream > #include < sstream > #include < map > #include < cmath > #include < fstream > #include < queue > #include < vector > #include < sstream > #include < cstring > #include < cstdio > #include < stack > #include < bitset > #include < ctime > #include < string > #include < cctype > #include < iomanip > #include < algorithm > using namespace std;#define INT long long int#define L(x)(x * 2)#define R(x)(x * 2 + 1) const int INF = 0x3f3f3f3f;
- const double esp = 0.0000000001;
- const double PI = acos( - 1.0);
- const int mod = 1000000007;
- const int MY = (1 << 5) + 5;
- const int MX = 100000 + 5;
- int n,
- m,
- nx,
- idx,
- num;
- int head[MX],
- ti[MX],
- siz[MX],
- son[MX],
- father[MX],
- top[MX],
- dep[MX];
- struct NODE {
- int u,
- v,
- w;
- }
- e[MX];
- struct MNODE {
- int u,
- v,
- w;
- }
- t[MX];
- struct Edge {
- int u,
- v,
- w,
- next;
- }
- E[MX * 2];
- void addedge(int u, int v, int w) {
- E[num].v = v;
- E[num].w = w;
- E[num].next = head[u];
- head[u] = num++;
- E[num].v = u;
- E[num].w = w;
- E[num].next = head[v];
- head[v] = num++;
- }
- bool cmp(NODE a, NODE b) {
- return a.w < b.w;
- }
- int find(int u) {
- if (father[u] != u) return find(father[u]);
- else return u;
- }
- void Kruskal() {
- nx = 1;
- int u,
- v,
- fa,
- fb;
- sort(e, e + m, cmp);
- for (int i = 0; i <= n; ++i) father[i] = i;
- for (int i = 0; i < m; ++i) {
- u = e[i].u;
- v = e[i].v;
- fa = find(u);
- fb = find(v);
- if (fa != fb) {
- father[fa] = fb;
- addedge(u, v, e[i].w);
- t[nx].u = u;
- t[nx].v = v;
- t[nx++].w = e[i].w;
- }
- }
- }
- void dfs_find(int u, int fa) {
- dep[u] = dep[fa] + 1;
- father[u] = fa;
- siz[u] = 1;
- son[u] = 0;
- for (int i = head[u]; i != -1; i = E[i].next) {
- int v = E[i].v;
- if (v == fa) continue;
- dfs_find(v, u);
- siz[u] += siz[v];
- if (siz[son[u]] < siz[v]) son[u] = v;
- }
- }
- void dfs_time(int u, int fa) {
- top[u] = fa;
- ti[u] = idx++;
- if (son[u]) dfs_time(son[u], top[u]);
- for (int i = head[u]; i != -1; i = E[i].next) {
- int v = E[i].v;
- if (v == father[u] || v == son[u]) continue;
- dfs_time(v, v);
- }
- }
- struct node {
- int le,
- rt,
- c;
- }
- T[MX * 4];
- void build(int i, int le, int rt) {
- T[i].le = le;
- T[i].rt = rt;
- T[i].c = 0;
- if (le == rt) return;
- int Mid = (le + rt) >> 1;
- build(L(i), le, Mid);
- build(R(i), Mid + 1, rt);
- }
- void update(int i, int pos, int w) {
- if (T[i].le == T[i].rt) {
- T[i].c = w;
- return;
- }
- int Mid = (T[i].le + T[i].rt) >> 1;
- if (pos <= Mid) update(L(i), pos, w);
- else update(R(i), pos, w);
- T[i].c = max(T[L(i)].c, T[R(i)].c);
- }
- int section(int i, int le, int rt) {
- if (T[i].le == le && T[i].rt == rt) return T[i].c;
- int Mid = (T[i].le + T[i].rt) >> 1;
- if (le > Mid) return section(R(i), le, rt);
- else if (rt <= Mid) return section(L(i), le, rt);
- else return max(section(L(i), le, Mid), section(R(i), Mid + 1, rt));
- }
- int LCA(int u, int v) {
- int ans = 0;
- while (top[u] != top[v]) {
- if (dep[top[u]] < dep[top[v]]) swap(u, v);
- ans = max(ans, section(1, ti[top[u]], ti[u]));
- u = father[top[u]];
- }
- if (dep[u] > dep[v]) swap(u, v);
- if (u != v) ans = max(ans, section(1, ti[u] + 1, ti[v]));
- return ans;
- }
- int main() {
- int u,
- v,
- Q;
- bool first = false;
- while (~scanf("%d%d", &n, &m)) {
- if (first) puts("");
- first = true;
- num = 0;
- memset(head, -1, sizeof(head));
- for (int i = 0; i < m; ++i) scanf("%d%d%d", &e[i].u, &e[i].v, &e[i].w);
- Kruskal();
- dep[1] = siz[0] = 0;
- dfs_find(1, 1);
- idx = 1;
- dfs_time(1, 1);
- build(1, 1, n);
- for (int i = 1; i < nx; ++i) {
- if (dep[t[i].u] < dep[t[i].v]) swap(t[i].u, t[i].v);
- update(1, ti[t[i].u], t[i].w);
- }
- scanf("%d", &Q);
- for (int i = 0; i < Q; ++i) {
- scanf("%d%d", &u, &v);
- printf("%d\n", LCA(u, v));
- }
- }
- return 0;
- }
倍增法 (类似 RMQ)
代码:
- #include < iostream > #include < sstream > #include < map > #include < cmath > #include < fstream > #include < queue > #include < vector > #include < sstream > #include < cstring > #include < cstdio > #include < stack > #include < bitset > #include < ctime > #include < string > #include < cctype > #include < iomanip > #include < algorithm > using namespace std;#define INT long long int#define L(x)(x * 2)#define R(x)(x * 2 + 1) const int INF = 0x3f3f3f3f;
- const double esp = 0.0000000001;
- const double PI = acos( - 1.0);
- const int mod = 1000000007;
- const int MY = (1 << 5) + 5;
- const int MX = 100000 + 5;
- const int S = 20;
- int n,
- m,
- idx,
- num,
- nx;
- int value[MX][25],
- p[MX][25],
- ti[MX],
- father[MX],
- dep[MX],
- head[MX];
- struct TEMP {
- int u,
- v,
- w;
- }
- A[MX];
- struct Edge {
- int v,
- w,
- next;
- }
- E[MX * 2];
- bool cmp(TEMP a, TEMP b) {
- return a.w < b.w;
- }
- int find(int u) {
- if (father[u] != u) return find(father[u]);
- return u;
- }
- void addedge(int u, int v, int w) {
- E[num].v = v;
- E[num].w = w;
- E[num].next = head[u];
- head[u] = num++;
- E[num].v = u;
- E[num].w = w;
- E[num].next = head[v];
- head[v] = num++;
- }
- void Kruskal() {
- nx = 1;
- int fa,
- fb;
- sort(A, A + m, cmp);
- for (int i = 0; i <= n; ++i) father[i] = i;
- for (int i = 0; i < m; ++i) {
- fa = find(A[i].u);
- fb = find(A[i].v);
- if (fa != fb) {
- father[fa] = fb;
- addedge(A[i].u, A[i].v, A[i].w);
- }
- }
- }
- void dfs_find(int u, int fa, int w) {
- dep[u] = dep[fa] + 1;
- p[u][0] = fa;
- value[u][0] = w;
- for (int i = 1; i <= S; ++i) {
- p[u][i] = p[p[u][i - 1]][i - 1];
- value[u][i] = max(value[u][i - 1], value[p[u][i - 1]][i - 1]);
- }
- for (int i = head[u]; i != -1; i = E[i].next) {
- int v = E[i].v;
- if (v == fa) continue;
- dfs_find(v, u, E[i].w);
- }
- }
- int LCA(int u, int v) {
- int ans = 0;
- if (dep[u] > dep[v]) swap(u, v);
- if (dep[u] < dep[v]) {
- int d = dep[v] - dep[u];
- for (int i = 0; i <= S; ++i) if (d & (1 << i)) {
- ans = max(ans, value[v][i]);
- v = p[v][i];
- }
- }
- if (u != v) {
- for (int i = S; i >= 0; --i) if (p[u][i] != p[v][i]) {
- ans = max(ans, value[u][i]);
- ans = max(ans, value[v][i]);
- u = p[u][i];
- v = p[v][i];
- }
- ans = max(ans, value[u][0]);
- ans = max(ans, value[v][0]);
- }
- return ans;
- }
- void init() {
- num = 0;
- memset(head, -1, sizeof(head));
- memset(ti, 0, sizeof(ti));
- memset(value, 0, sizeof(value));
- memset(p, 0, sizeof(p));
- memset(dep, 0, sizeof(dep));
- }
- int main() {
- //freopen("input.txt" ,"r" ,stdin) ;
- int u,
- v,
- Q;
- bool first = false;
- while (~scanf("%d%d", &n, &m)) {
- if (first) puts("");
- first = true;
- init();
- for (int i = 0; i < m; ++i) scanf("%d%d%d", &A[i].u, &A[i].v, &A[i].w);
- Kruskal();
- dep[1] = 0;
- dfs_find(1, 1, 0);
- scanf("%d", &Q);
- while (Q--) {
- scanf("%d%d", &u, &v);
- printf("%d\n", LCA(u, v));
- }
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2230885.html