문제를 요약하면, 주어진 그래프의 2개의 트리로 구성된 포레스트 중 에지의 가중치의 합이 최소인 것의 그 가중치를 구하는 문제이다.
이는 그래프의 MST를 구하는 과정 중 마지막 에지를 더하는 단계를 생략하는 것으로 구할 수 있다.
아래는 제출한 소스코드이다.
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
int uf[100001];
int findf(int x) {
if (x == uf[x]) return x;
return uf[x] = findf(uf[x]);
}
struct edge {
ll w;
int x, y;
void mod(ll weight, int xx, int yy) {
w = weight, x = xx, y = yy;
}
};
bool comp(edge e1, edge e2) {
return e1.w < e2.w;
}
edge edges[1000000];;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int N, M; cin >> N >> M;
for (int i = 1; i <= N; i++) uf[i] = i;
for (int i = 0;i < M;i++) {
int x, y; ll w; cin >> x >> y >> w;
edges[i].mod(w, x, y);
}
sort(edges, edges + M, comp);
ll ans = 0;
int cnt = 0;
for (int i = 0; i < M; i++) {
if (cnt == N - 2) break;
int x = findf(edges[i].x), y = findf(edges[i].y);
if (x == y) continue;
ans += edges[i].w;
uf[y] = x;
cnt++;
}
cout << ans;
}
볼록다각형의 삼각분할이 주어질 때, 각 삼각형을 노드로 하고 변을 공유하는 삼각형들의 노드 사이에 에지를 그으면 그 그래프는 트리가 됨을 알 수 있다. (사이클이 존재한다면, 공유하는 하나의 꼭짓점이 존재하는 사이클이 존재하고 이는 볼록다각형의 꼭짓점만을 사용한 분할이 아니게 되기 때문이다.)
이 트리를 구현하고, 같은 색을 가진 꼭짓점 사이에 있는 에지를 모두 "자를 수 없는 에지"로 표시하여 문제를 해결할 수 있다. 글쓴이는 이를 HLD(heavy-light decomposition)와 지연전파(lazy propagation)를 이용한 세그먼트 트리(segment tree)로 해결하였다.
HLD를 이용하여 에지를 관리할 때 루트방향이 어느 쪽인지 혼동하는 실수를 줄여야하는데...
아래는 제출한 소스코드이다.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> G[100001];
vector<int> colors[100001];
vector <pair<pair<int, int>, int>> edges;
int heavychild[100001];
int dfs(int current, int parent) {
int childcnt = 1;
int hchild = -1;
int hcount = -1;
for (auto node : G[current]) {
if (node == parent) continue;
int temp = dfs(node, current);
childcnt += temp;
if (temp > hcount) {
hcount = temp;
hchild = node;
}
}
heavychild[current] = hchild;
return childcnt;
}
int nodeidx[100001];
int chainidx[100001];
int cnth[100001];
int cparent[100001];
int cdepth[100001];
int nidx = 1, cidx = 1;
void hld(int current, int parent, int cn, int cp, int cd) {
nodeidx[current] = nidx;
chainidx[nidx] = cidx;
cnth[nidx] = cn;
cparent[nidx] = cp;
cdepth[nidx] = cd;
int hchild = heavychild[current];
if (hchild > 0) {
nidx++;
hld(hchild, current, cn + 1, cp, cd);
}
cd++;
for (auto node : G[current]) {
if (node == parent || node == hchild) continue;
nidx++; cidx++;
hld(node, current, 0, nodeidx[current], cd);
}
}
int seg[262145];
bool lazy[262145];
void propagate(int L, int R, int sI) {
seg[sI] = (R - L + 1);
if (L < R) {
lazy[sI * 2] = 1;
lazy[sI * 2 + 1] = 1;
}
lazy[sI] = 0;
}
int update(int L, int R, int qL, int qR, int sI) {
if (lazy[sI]) propagate(L, R, sI);
if (R < qL || qR < L) return seg[sI];
if (qL <= L && R <= qR) {
lazy[sI] = 1;
propagate(L, R, sI);
return seg[sI];
}
return seg[sI] = update(L, (L + R) / 2, qL, qR, sI * 2) + update((L + R) / 2 + 1, R, qL, qR, sI * 2 + 1);
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int N; cin >> N;
for (int i = 3; i <= N; i++) {
int a, b, c, d; cin >> a >> b >> c >> d;
colors[d].push_back(i);
if (a < b) edges.push_back({ {a,b},i });
else edges.push_back({ {b,a},i });
if (b < c) edges.push_back({ {b,c},i });
else edges.push_back({ {c,b},i });
if (c < a) edges.push_back({ {c,a},i });
else edges.push_back({ {a,c},i });
}
sort(edges.begin(), edges.end());
int esize = edges.size();
for (int i = 1; i < esize; i++) {
if ((edges[i - 1].first.first == edges[i].first.first) && (edges[i - 1].first.second == edges[i].first.second)) {
int x = edges[i - 1].second, y = edges[i].second;
G[x].push_back(y);
G[y].push_back(x);
}
}
dfs(N, 0);
hld(N, 0, 0, 0, 0);
for (int i = 1; i <= N; i++) {
int cnt = colors[i].size();
for (int k = 1; k < cnt; k++) {
int x = nodeidx[colors[i][k - 1]], y = nodeidx[colors[i][k]];
if (cdepth[x] != cdepth[y]) {
if (cdepth[x] < cdepth[y]) swap(x, y);
while (cdepth[x] > cdepth[y]) {
update(1, N, x - cnth[x], x, 1);
x = cparent[x];
}
}
while (chainidx[x] != chainidx[y]) {
update(1, N, x - cnth[x], x, 1);
update(1, N, y - cnth[y], y, 1);
x = cparent[x], y = cparent[y];
}
if (x > y) swap(x, y);
if (x < y) update(1, N, x + 1, y, 1);
}
}
cout << N - 3 - seg[1];
}
한 방향의 대각선으로 움직일 수 있는 범위를 하나의 노드로 생각하여, 서로 다른 방향의 두 대각선에 대해 둘이 공통된 칸을 지난다면 그 두 대각선범위 사이에 에지가 있는 것으로 보아 이분그래프(bipartite graph)를 구할 수 있다. 이 이후는 단순한 maximum bipartite matching 문제이다.
움직일 수 있는 범위로 대각선을 나누는 것에 대한 구현을 잘 해주자.
아래는 제출한 소스코드이다.
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
bool board[100][100];
int diag1[100][100];
int diag2[100][100];
vector<int> G[5001];
int visited[5001];
int matching[5001];
int bipartite(int current) {
if (visited[current]) return 0;
visited[current] = 1;
for (auto node : G[current]) {
if (matching[node] == 0) {
matching[node] = current;
return 1;
}
if (bipartite(matching[node])) {
matching[node] = current;
return 1;
}
}
return 0;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int N, M; cin >> N >> M;
while (M--) {
int r, c; cin >> r >> c;
r--; c--;
board[r][c] = 1;
}
int idx = 1;
for (int i = 0; i < N; i++) {
for (int k = 0; k <= i; k++) {
if (board[i - k][k]) idx++;
else diag1[i - k][k] = idx;
}
idx++;
}
for (int i = 0; i < N - 1; i++) {
for (int k = 0; k <= i; k++) {
if (board[N - 1 - i + k][N - 1 - k]) idx++;
else diag1[N - 1 - i + k][N - 1 - k] = idx;
}
idx++;
}
idx = 1;
for (int i = 0; i < N; i++) {
for (int k = 0; k < N - i; k++) {
if (board[i + k][k]) idx++;
else diag2[i + k][k] = idx;
}
idx++;
}
for (int i = 1; i < N; i++) {
for (int k = 0; k < N - i; k++) {
if (board[k][i + k]) idx++;
else diag2[k][i + k] = idx;
}
idx++;
}
for (int r = 0; r < N; r++) {
for (int c = 0; c < N; c++) {
if (board[r][c]) continue;
G[diag1[r][c]].push_back(diag2[r][c]);
}
}
int ans = 0;
for (int i = 1; i <= 5000; i++) {
memset(visited, 0, sizeof(visited));
ans += bipartite(i);
}
cout << ans;
}
모든 가로단어끼리와 세로단어끼리는 겹치지 않는다고 조건에 주어져있으므로, 각 가로단어와 세로단어를 노드로 생각하고 퍼즐 위에서 겹치는 칸의 글자가 서로 다른 두 단어끼리 간선을 이어주면 이분그래프(bipartite graph)를 하나 만들 수 있다. 이 그래프에서 최대한 많은 단어를 적어넣을 때의 경우의 수를 구하는 것은 위에서 구한 이분그래프에서 노드의 최대 독립 집합(maximum independent set)의 크기를 찾는 문제로 볼 수 있고, 이분그래프에서 이는 maximum bipartite matching의 수를 이용하여 간단히 계산할 수 있다.
아래는 제출한 소스코드이다.
#include <iostream>
#include <vector>
#include <string>
#include <cstring>
using namespace std;
int board[2001][2001][2];
vector<int> G[501];
int visited[501];
int matching[501];
int bipartite(int current) {
if (visited[current]) return 0;
visited[current] = 1;
for (auto node : G[current]) {
if (matching[node] == 0) {
matching[node] = current;
return 1;
}
if (bipartite(matching[node])) {
matching[node] = current;
return 1;
}
}
return 0;
}
void solve() {
for (int i = 1; i <= 500; i++) G[i].clear();
memset(matching, 0, sizeof(matching));
memset(board, 0, sizeof(board));
int garo, sero; cin >> garo >> sero;
for (int i = 1; i <= garo; i++) {
int x, y; string s; cin >> x >> y >> s;
int slen = s.length();
for (int k = 0; k < slen; k++) {
board[y][x + k][0] = s[k], board[y][x + k][1] = i;
}
}
for (int i = 1; i <= sero; i++) {
int x, y; string s; cin >> x >> y >> s;
int slen = s.length();
for (int k = 0; k < slen; k++) {
if (board[y + k][x][0] != s[k]) {
G[board[y + k][x][1]].push_back(i);
}
}
}
int ans = 0;
for (int i = 1; i <= garo; i++) {
memset(visited, 0, sizeof(visited));
ans += bipartite(i);
}
cout << garo + sero - ans << '\n';
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int T; cin >> T;
while (T--) {
solve();
}
}
한 열에 룩을 하나씩만 놓을 수 있으므로, 각 행마다 겹치지 않게 열을 하나씩 최대한 고르면서 가능한 한 많은 열을 고르는 것으로 문제를 생각할 수 있다. 이 상황은 각 행과 열을 노드로 하는 이분그래프(bipartite graph)로 모델링을 할 수 있다. 이 그래프에서 maximum bipartite matching 알고리즘을 이용하면 문제를 해결할 수 있다.
아래는 제출한 소스코드이다.
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
bool board[301][301];
vector<int> G[301];
int visited[301];
int matching[301];
int bipartite(int current) {
if (visited[current]) return 0;
visited[current] = 1;
for (auto node : G[current]) {
if (matching[node] == 0) {
matching[node] = current;
return 1;
}
if (bipartite(matching[node])) {
matching[node] = current;
return 1;
}
}
return 0;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int R, C, N; cin >> R >> C >> N;
while (N--) {
int x, y; cin >> x >> y;
board[x][y] = 1;
}
for (int r = 1; r <= R; r++) {
for (int c = 1; c <= C; c++) {
if (board[r][c]) continue;
G[r].push_back(c);
}
}
int ans = 0;
for (int i = 1; i <= R; i++) {
memset(visited, 0, sizeof(visited));
ans += bipartite(i);
}
cout << ans;
}