BOJ 13208 승현이와 승현이
출처 : https://www.acmicpc.net/problem/13208
문제에서 그래프가 주어진다.
이걸 또 다른 그래프로 바꿔야 한다.
주어진 그래프에서는 노드가 1, 2, 3, ,,, N까지 있다.
여기서 새로 만들어야 될 그래프는 N^2개의 노드를 가진다.
(1, 1), (1, 2), (1, 3) ,,, (1, N), (2, 1), (2, 2),,,(2, N),,,(N, N)
이것을 다시 1, 2, 3, ,,, N^2로 인덱싱 해준다.
여기서 새로만든 (a, b)노드의 정의는 문제를 그대로 따오자면
조승현13이 a번 노드에 있고, 조승현16이 b번 노드에 있는 '상태'를 나타내는 노드다.
그럼 노드정의는 다 대었으니 노드사이의 간선cost를 구해야 한다.
아무리 생각해도 글로는 좀 힘들것 같아서 그림을 준비해 봄.
아래그림은 입력과 동일
현재 조승현13(이하 U), 조승현16(이하 V)가 각각 1번, 4번 노드에 있는 상황
(원 안에 있는 숫자는 노드번호, 원 밖에 있는 숫자는 C_i)
이때 cost는 5 * 100 = 500
여기서 V가 움직인다면.
V는 5번 노드에 있고 C_5는 12, 이때 new_cost는 5 * 12 = 60
그러면
(1, 4) (1, 5) 노드 사이의 cost는 max(500, 60) = 500
max(500, 12) = 500 값이여야 U, V가 (1, 4)이던 (1, 5)이던 서로 통신을 할 수 있기 때문
마찬가지로
U도 옮겨 가면서 새로 그래프를 만들어 준다.
위의 그림은 (1, 4) 노드와 (2, 4) 노드를 잇는 엣지 cost는 max(500, 100) = 500이 됨
이렇게 새로운 그래프를 구성하고 새로 만들어진 그래프에서 MST를 구성한다.
이후 쿼리 처리는 만들어진 MST에서 (S, E)노드로 부터 (E, S)노드로 가는 경로중 최대값을 구하는 문제로 바뀌게 됨.
이는 LCA를 이용하면 구할 수 있음
으아..
아래는 코드
#include<bits/stdc++.h>
#define endl "\n"
using namespace std;
using ll = long long;
struct G
{
struct edge
{
int a, b, f, c;
bool operator < (const edge& a) const
{
return c < a.c;
}
};
vector<edge> el;
vector<vector<int>>elist, table, olist;
vector<int> size, parent, chain_num, chain_depth, chain_idx, cindex, dnum, info;
int ovn, oen, vn, num;
G(int a, int b) : ovn(a), oen(b), vn(a * a), num(0)
{
olist.resize(ovn + 1);
size.resize(vn + 1, 0);
parent.resize(vn + 1, 0);
chain_num.resize(vn + 1, 0);
chain_depth.resize(vn + 1, 0);
chain_idx.resize(vn + 1, 0);
cindex.resize(vn + 1, 0);
dnum.resize(vn + 1, 0);
info.resize(ovn + 1);
fill_table();
input();
ex_e();
elist.resize(vn + 1);
}
void input()
{
int i, a, b;
for (i = 1; i <= ovn; i++)
{
cin >> info[i];
}
for (i = 0; i < oen; i++)
{
cin >> a >> b;
olist[a].push_back(b);
olist[b].push_back(a);
}
}
void fill_table()
{
int i, j, c;
table.resize(ovn + 1);
for (i = c = 1; i <= ovn; i++)
{
table[i].resize(ovn + 1);
for (j = 1; j <= ovn; j++)
{
table[i][j] = c++;
}
}
}
void ex_e()
{
int u, v, cur, next, d, st, nc, m;
for (u = 1; u <= ovn; u++)
{
for (v = 1; v <= ovn; v++)
{
cur = table[u][v];
st = info[u] * info[v];
for (auto& nn : olist[u])
{
next = table[nn][v];
nc = info[v] * info[nn];
m = max(st, nc);
el.push_back({ cur, next, 0, m });
}
for (auto& nn : olist[v])
{
next = table[u][nn];
nc = info[u] * info[nn];
m = max(st, nc);
el.push_back({ cur, next, 0, m });
}
}
}
for (int i = 0; i < ovn; i++)
{
olist.clear();
}
olist.clear();
}
void pb(int a, int b)
{
elist[a].push_back(b);
}
void build_hld()
{
go1(1, 0);
go2(1, 0, 1, 0);
for (int i = 0; i <= vn; i++)
{
elist[i].clear();
}
elist.clear();
size.clear();
}
int go1(int c, int p)
{
size[c] = 1;
parent[c] = p;
for (auto& nx : elist[c])
{
if (nx != p)
{
size[c] += go1(nx, c);
}
}
return size[c];
}
void go2(int c, int p, int ccn, int ccd)
{
int h = -1;
dnum[c] = ++num;
chain_num[c] = ccn;
chain_depth[c] = ccd;
chain_idx[c] = cindex[ccn]++;
for (auto& nx : elist[c])
{
if (nx != p && (h == -1 || size[nx] > size[h]))
{
h = nx;
}
}
if (h != -1)
{
go2(h, c, ccn, ccd);
}
for (auto& nx : elist[c])
{
if (nx != p && nx != h)
{
go2(nx, c, nx, ccd + 1);
}
}
}
int lca(int a, int b)
{
while (chain_num[a] != chain_num[b])
{
if (chain_depth[a] > chain_depth[b])
{
a = parent[chain_num[a]];
}
else
{
b = parent[chain_num[b]];
}
}
return chain_idx[a] > chain_idx[b] ? b : a;
}
};
struct UNION_FIND
{
int vn;
vector<int>r, p;
UNION_FIND(int a) :vn(a)
{
r.resize(vn + 1, 0);
p.resize(vn + 1);
for (int i = 0; i <= vn; i++)
{
p[i] = i;
}
}
int find(int x)
{
if (x == p[x])
{
return x;
}
return p[x] = find(p[x]);
}
void uni(int x, int y)
{
lnk(find(x), find(y));
}
void lnk(int x, int y)
{
if (r[x] > r[y])
{
p[y] = x;
}
else
{
p[x] = y;
if (r[x] == r[y])
{
r[y]++;
}
}
}
};
struct SEGMENT_TREE
{
int n, node, s, e, l, r, g;
vector<int>tree;
SEGMENT_TREE(int a) : n(a)
{
for (node = s = l = r = 1; r - l + 1 < n; l <<= 1, r <<= 1, r |= 1);
tree.resize(r + 1, 0);
e = r - l + 1;
g = l - 1;
}
void update(int idx, int val)
{
tree[idx] = val;
idx >>= 1;
while (idx)
{
tree[idx] = max(tree[idx << 1], tree[idx << 1 | 1]);
idx >>= 1;
}
}
int query(int node, int start, int end, int left, int right)
{
int mid;
if (left > end || right < start)
{
return 0;
}
if (left <= start && end <= right)
{
return tree[node];
}
mid = (start + end) >> 1;
return max(query(node << 1, start, mid, left, right), query(node << 1 | 1, mid + 1, end, left, right));
}
};
struct SOLUTION
{
int ovn, en;
struct G g;
UNION_FIND uf;
SEGMENT_TREE seg;
SOLUTION(int a, int b) : ovn(a), en(b), g(a, b), uf(a * a), seg(a * a)
{
make_mst();
g.build_hld();
fill_seg();
proc();
}
void make_mst()
{
sort(g.el.begin(), g.el.end());
for (auto& [a, b, f, c] : g.el)
{
if (uf.find(a) != uf.find(b))
{
f = 1;
g.pb(a, b);
g.pb(b, a);
uf.uni(a, b);
}
}
}
void fill_seg()
{
for (auto& [a, b, f, c] : g.el)
{
if (f)
{
seg.update(seg.g + g.dnum[g.parent[a] == b ? a : b], c);
}
}
g.el.clear();
}
void proc()
{
int qn, a, b;
cin >> qn;
while (qn--)
{
cin >> a >> b;
cout << query(a, b) << endl;
}
}
int query(int a, int b)
{
int l;
l = g.lca(g.table[a][b], g.table[b][a]);
return max(hq(l, g.table[a][b]), hq(l, g.table[b][a]));
}
int hq(int a, int b)
{
int ans = 0;
while (g.chain_num[a] != g.chain_num[b])
{
ans = max(ans, seg.query(seg.node, seg.s, seg.e, g.dnum[g.chain_num[b]], g.dnum[b]));
b = g.parent[g.chain_num[b]];
}
return max(ans, seg.query(seg.node, seg.s, seg.e, g.dnum[a] + 1, g.dnum[b]));
}
};
int main(void)
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int ovn, en;
cin >> ovn >> en;
SOLUTION sol(ovn, en);
return 0;
}