傳送門
這道題,先用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
{
int x, y, z;
}tree[100001];
struct Node
{
int next, to, val;
}edge[100001];
inline void add(int a, int b, int c)
{
edge[cnt].val = c;
edge[cnt].to = b;
edge[cnt].next = head[a];
head[a] = cnt++;
}
inline int father(int a)
{
return a == f[a] ? a : f[a] = father(f[a]);
}
inline bool cmp(node a, node b)
{
return a.z > b.z;
}
void kruskal()
{
int i;
for(i = 1; i <= m; i++) scanf("%d %d %d", &tree[i].x, &tree[i].y, &tree[i].z);
for(i = 1; i <= n; i++) f[i] = i;
std::sort(tree + 1, tree + m + 1, cmp);
for(i = 1; i <= m; i++)
{
int fa = father(tree[i].x), fb = father(tree[i].y);
if(fa != fb)
{
f[fa] = fb;
add(tree[i].x, tree[i].y, tree[i].z);
add(tree[i].y, tree[i].x, tree[i].z);
}
if(k == n - 1) break;
}
}
void dfs(int i)
{
int j;
vis[i] = 1;
for(j = head[i]; j != -1; j = edge[j].next)
if(!vis[edge[j].to])
{
deep[edge[j].to] = deep[i] + 1;
p[edge[j].to][0] = i;
minn[edge[j].to][0] = edge[j].val;
dfs(edge[j].to);
}
}
void init()
{
int i, j;
for(j = 1; (1 << j) <= n; j++)
for(i = 1; i <= n; i++)
{
p[i][j] = p[p[i][j - 1]][j - 1];
minn[i][j] = std::min(minn[i][j - 1], minn[p[i][j - 1]][j - 1]);
}
}
int lca(int a, int b)
{
int i, j, ret = 707406378;
if(deep[a] < deep[b]) std::swap(a, b);
for(i = 0; (1 << i) <= deep[a]; i++);
i--;
for(j = i; j >= 0; j--)
if(deep[a] - (1 << j) >= deep[b])
{
ret = std::min(ret, minn[a][j]);
a = p[a][j];
}
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][j], minn[b][j]));
a = p[a][j];
b = p[b][j];
}
ret = std::min(ret, std::min(minn[a][0], minn[b][0]));
return ret;
}
int main()
{
int i, j, x1, y1;
scanf("%d %d", &n, &m);
memset(head, -1, sizeof(head));
//memset(minn, 127 / 3, sizeof(minn));
kruskal();
for(i = 1; i <= n; i++)
if(!vis[i])
{
deep[i] = 1;
dfs(i);
}
init();
scanf("%d", &q);
for(i = 1; i <= q; i++)
{
scanf("%d %d", &x1, &y1);
if(father(x1) != father(y1)) printf("-1\n");
else printf("%d\n", lca(x1, y1));
}
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 = 707406378;
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 {
12 int x, y, z;
13 }p[MAXM];
14
15 inline bool cmp(node a, node b)
16 {
17 return a.z > b.z;
18 }
19
20 inline void add(int x, int y, int z)
21 {
22 to[cnt] = y;
23 val[cnt] = z;
24 next[cnt] = head[x];
25 head[x] = cnt++;
26 }
27
28 inline int find(int x)
29 {
30 return x == f1[x] ? x : f1[x] = find(f1[x]);
31 }
32
33 inline int Min(int x, int y)
34 {
35 return x < y ? x : y;
36 }
37
38 inline void swap(int &x, int &y)
39 {
40 x ^= y ^= x ^= y;
41 }
42
43 inline void dfs(int u)
44 {
45 int i, v;
46 deep[u] = deep[f[u][0]] + 1;
47 for(i = 0; f[u][i]; i++)
48 f[u][i + 1] = f[f[u][i]][i],
49 min[u][i + 1] = Min(min[u][i], min[f[u][i]][i]);
50 for(i = head[u]; i ^ -1; i = next[i])
51 {
52 v = to[i];
53 if(!deep[v])
54 {
55 f[v][0] = u;
56 min[v][0] = val[i];
57 dfs(v);
58 }
59 }
60 }
61
62 inline int lca(int x, int y)
63 {
64 int i, ans = INF;
65 if(deep[x] < deep[y]) swap(x, y);
66 for(i = 20; i >= 0; i--)
67 if(deep[f[x][i]] >= deep[y])
68 ans = Min(ans, min[x][i]), x = f[x][i];
69 if(x == y) return ans == INF ? -1 : ans;
70 for(i = 20; i >= 0; i--)
71 if(f[x][i] ^ f[y][i])
72 ans = Min(ans, min[x][i]),
73 ans = Min(ans, min[y][i]),
74 x = f[x][i], y = f[y][i];
75 ans = Min(ans, min[x][0]);
76 ans = Min(ans, min[y][0]);
77 return ans == INF ? -1 : ans;
78 }
79
80 int main()
81 {
82 //freopen("truck.in", "r", stdin);
83 //freopen("truck.out", "w", stdout);
84 int i, x, y, fx, fy;
85 scanf("%d %d", &n, &m);
86 memset(head, -1, sizeof(head));
87 memset(min, 127 / 3, sizeof(min));
88 for(i = 1; i <= m; i++) scanf("%d %d %d", &p[i].x, &p[i].y, &p[i].z);
89 std::sort(p + 1, p + m + 1, cmp);
90 for(i = 1; i <= n; i++) f1[i] = i;
91 for(i = 1; i <= m; i++)
92 {
93 fx = find(p[i].x);
94 fy = find(p[i].y);
95 if(fx ^ fy)
96 {
97 f1[fx] = fy;
98 tot++;
99 add(p[i].x, p[i].y, p[i].z);
100 add(p[i].y, p[i].x, p[i].z);
101 }
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 {
110 scanf("%d %d", &x, &y);
111 if(find(x) ^ find(y)) puts("-1");
112 else printf("%d\n", lca(x, y));
113 }
114 return 0;
115 }
View Code
轉載于:https://www.cnblogs.com/zhenghaotian/p/6667614.html