Written by nodejs-style
on 2021-07-26

2021년 정올 본선 2번 그래프 균형 맞추기

루트의 가중치를 미리 0으로 정해둔다고 생각해봅시다. 그러면 루트와 이어진 정점들은 간선과 같은 가중치를 가지게 되고 그와 이어진 정점들도 간선 가중치 - 이전 정점 가중치가 부여되게 됩니다. 따라서 모든 정점들은 루트에 의해 가중치가 고정되고 이는 dfs 한번에 구할 수 있습니다.

좀더 자세히 살펴보면 루트로부터의 거리가 홀수면 루트의 가중치가 늘어남에 따라 같이 늘어나고 짝수면 반대로 줄어들게 됩니다.

절댓값의 합을 구하기 때문에 루트의 값이 너무 커지거나 작아지면 최솟값을 구할 수 없고 따라서 그 사이를 삼분탐색으로 구할수 있을 거라는 생각을 했습니다.

처음에는 트리로 문제를 잘못봐서 삼분탐색만 생각했는데 사이클이 있을 수 있었습니다.

앞서말한 거리에 따라 정점들을 증가와 감소로 경우를 나누어 생각하면 처음 dfs를 돌 때 같은 정점에서 증가인지 감소인지 여부까지 같으면서 서로 다른 정점에서 탐색할 때의 가중치가 다르면 루트의 가중치와 관계없이 조건을 만족할 수 없기에 No를 출력해야 합니다.

그리고 한 정점에서 증가와 감소의 경우를 모두 탐색했을때는 이 둘을 같게 만들어 주어야 하기 때문에 (감소 가중치 - 증가 가중치) / 2가 루트의 가중치로 고정되고 이 값이 여러가지 이거나 차이가 홀수여서 2로 나눌 수 없는 경우도 No로 처리를 해 주어야 합니다.

3시 30분 4초 제출, 6점

#include #include #include #include using namespace std; vector>> graph; vector cj1, cj2; vector visited1, visited2; bool flag = true; long long int dfs(int a, int b, int c){ if (c == 1){ visited1[a] = true; long long int ret = abs(cj1[a]); for (pair& i : graph[a]){ if (i.first == b) continue; if (visited2[i.first]){ if (cj2[i.first] != i.second - cj1[a]) flag = false; continue; } cj2[i.first] = i.second - cj1[a]; ret += dfs(i.first, a, 2); } return ret; } else{ visited2[a] = true; long long int ret = abs(cj2[a]); for (pair& i : graph[a]){ if (i.first == b) continue; if (visited1[i.first]){ if (cj1[i.first] != i.second - cj2[a]) flag = false; continue; } cj1[i.first] = i.second - cj2[a]; ret += dfs(i.first, a, 1); } return ret; } } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int N, M, a, b, l = 0, r = 2000000, ans; long long int c; cin >> N >> M; cj1.resize(N); cj2.resize(N); graph.resize(N); while (M--){ cin >> a >> b >> c; graph[--a].push_back({--b, c}); graph[b].push_back({a, c}); } visited1.resize(N); visited2.resize(N); dfs(0, -1, 1); bool cycle = false; int needto = 0; for (int i = 0; i < N; i++){ if (visited1[i] && visited2[i]){ if ((cj2[i] - cj1[i]) % 2) flag = false; else if (!cycle || (cj2[i] - cj1[i]) / 2 == needto) needto = (cj2[i] - cj1[i]) / 2; else flag = false; cycle = true; } } if (!flag){ cout << "No"; return 0; } else if (cycle){ cout << "Yes

"; visited1.clear(); visited2.clear(); visited1.resize(N); visited2.resize(N); cj1[0] = needto; dfs(0, -1, 1); for (int i = 0; i < N; i++){ if (visited1[i]) cout << cj1[i] << ' '; else cout << cj2[i] << ' '; } return 0; } while (1){ if (l + 10 >= r){ ans = l - 1000000; cj1[0] = l - 1000000; visited1.clear(); visited2.clear(); visited1.resize(N); visited2.resize(N); long long int value = dfs(0, -1, 1); for (int i = l + 1; i <= r; i++){ cj1[0] = i - 1000000; visited1.clear(); visited2.clear(); visited1.resize(N); visited2.resize(N); long long int tmp = dfs(0, -1, 1); if (tmp < value){ ans = i - 1000000; value = tmp; } } break; } int tt = (r - l) / 3, mid1 = l + tt, mid2 = r - tt; long long int ll, rr; cj1[0] = mid1 - 1000000; visited1.clear(); visited2.clear(); visited1.resize(N); visited2.resize(N); ll = dfs(0, -1, 1); cj1[0] = mid2 - 1000000; visited1.clear(); visited2.clear(); visited1.resize(N); visited2.resize(N); rr = dfs(0, -1, 1); if (ll < rr) r = mid2 - 1; else l = mid1 + 1; } cj1[0] = ans; visited1.clear(); visited2.clear(); visited1.resize(N); visited2.resize(N); dfs(0, -1, 1); cout << "Yes

"; for (int i = 0; i < N; i++){ if (visited1[i]) cout << cj1[i] << ' '; else cout << cj2[i] << ' '; } return 0; }

3개의 정점이 사이클을 이루는 그래프에서만 ac가 떴습니다. 삼분탐색 부분에서 문제가 있는것 같았는데 생각해보니 간선의 가중치의 절댓값 보다 정점의 가중치의 절댓값이 커질 수 가 있었습니다. 따라서 넉넉잡아 절댓값 10^11을 범위로 잡았는데 들어보니 int 범위 안에서는 해결이 되지 않는다고 합니다.

4시 23초 제출, 68점

#include #include #include #include using namespace std; vector>> graph; vector cj1, cj2; vector visited1, visited2; int no = 1; bool flag = true; long long int dfs(int a, int b, int c){ if (c == 1){ visited1[a] = no; long long int ret = abs(cj1[a]); for (pair& i : graph[a]){ if (i.first == b) continue; if (visited2[i.first] == no){ if (cj2[i.first] != i.second - cj1[a]) flag = false; continue; } cj2[i.first] = i.second - cj1[a]; ret += dfs(i.first, a, 2); } return ret; } else{ visited2[a] = no; long long int ret = abs(cj2[a]); for (pair& i : graph[a]){ if (i.first == b) continue; if (visited1[i.first] == no){ if (cj1[i.first] != i.second - cj2[a]) flag = false; continue; } cj1[i.first] = i.second - cj2[a]; ret += dfs(i.first, a, 1); } return ret; } } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int N, M, a, b; long long int l = 0, r = 200000000000, ans, c; cin >> N >> M; cj1.resize(N); cj2.resize(N); graph.resize(N); while (M--){ cin >> a >> b >> c; graph[--a].push_back({--b, c}); graph[b].push_back({a, c}); } visited1.resize(N); visited2.resize(N); dfs(0, -1, 1); bool cycle = false; int needto = 0; for (int i = 0; i < N; i++){ if (visited1[i] == no && visited2[i] == no){ if ((cj2[i] - cj1[i]) % 2) flag = false; else if (!cycle || (cj2[i] - cj1[i]) / 2 == needto) needto = (cj2[i] - cj1[i]) / 2; else flag = false; cycle = true; } } if (!flag){ cout << "No"; return 0; } else if (cycle){ cout << "Yes

"; no++; cj1[0] = needto; dfs(0, -1, 1); for (int i = 0; i < N; i++){ if (visited1[i] == no) cout << cj1[i] << ' '; else cout << cj2[i] << ' '; } return 0; } while (1){ if (l + 10 >= r){ ans = l - 100000000000; cj1[0] = l - 100000000000; no++; long long int value = dfs(0, -1, 1); for (long long int i = l + 1; i <= r; i++){ cj1[0] = i - 100000000000; no++; long long int tmp = dfs(0, -1, 1); if (tmp < value){ ans = i - 100000000000; value = tmp; } } break; } long long int tt = (r - l) / 3, mid1 = l + tt, mid2 = r - tt; long long int ll = 0, rr = 0; cj1[0] = mid1 - 100000000000; no++; ll = dfs(0, -1, 1); cj1[0] = mid2 - 100000000000; no++; rr = dfs(0, -1, 1); if (ll < rr) r = mid2 - 1; else l = mid1 + 1; } cj1[0] = ans; no++; dfs(0, -1, 1); cout << "Yes

"; for (int i = 0; i < N; i++){ if (visited1[i] == no) cout << cj1[i] << ' '; else cout << cj2[i] << ' '; } return 0; }

사이클 처리에서 노드 가중치의 int 범위 초과를 고려하지 않았습니다.

4시 2분 4초 제출, 100점

#include #include #include #include using namespace std; vector>> graph; vector cj1, cj2; vector visited1, visited2; int no = 1; bool flag = true; long long int dfs(int a, int b, int c){ if (c == 1){ visited1[a] = no; long long int ret = abs(cj1[a]); for (pair& i : graph[a]){ if (i.first == b) continue; if (visited2[i.first] == no){ if (cj2[i.first] != i.second - cj1[a]) flag = false; continue; } cj2[i.first] = i.second - cj1[a]; ret += dfs(i.first, a, 2); } return ret; } else{ visited2[a] = no; long long int ret = abs(cj2[a]); for (pair& i : graph[a]){ if (i.first == b) continue; if (visited1[i.first] == no){ if (cj1[i.first] != i.second - cj2[a]) flag = false; continue; } cj1[i.first] = i.second - cj2[a]; ret += dfs(i.first, a, 1); } return ret; } } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int N, M, a, b; long long int l = 0, r = 200000000000, ans, c; cin >> N >> M; cj1.resize(N); cj2.resize(N); graph.resize(N); while (M--){ cin >> a >> b >> c; graph[--a].push_back({--b, c}); graph[b].push_back({a, c}); } visited1.resize(N); visited2.resize(N); dfs(0, -1, 1); bool cycle = false; long long int needto = 0; for (int i = 0; i < N; i++){ if (visited1[i] == no && visited2[i] == no){ if ((cj2[i] - cj1[i]) % 2) flag = false; else if (!cycle || (cj2[i] - cj1[i]) / 2 == needto) needto = (cj2[i] - cj1[i]) / 2; else flag = false; cycle = true; } } if (!flag){ cout << "No"; return 0; } else if (cycle){ cout << "Yes

"; for (int i = 0; i < N; i++){ if (visited1[i] == no) cout << cj1[i] << ' '; else cout << cj2[i] << ' '; } return 0; }

from http://owsjdhdusiwi.tistory.com/15 by ccl(A) rewrite - 2021-07-26 18:26:13

Top