K. Traffic Jams

자동차가 C대 있고 각 자동차의 시작 위치가 다를 수 있다. 모든 자동차의 목적지는 1번 마을이고, 각 자동차는 최단 경로 중 임의의 한 경로로 이동한다고 하자. 두 자동차가 동시에 같은 마을에서 같은 도로를 이동할 수 없을 때, 목적지에 갈 수 있는 자동차의 최대 개수를 구하는 문제다.

이 문제는 2013년 월드 파이널 C번 문제와 지문 하나 다르지 않게 출제되었다. 다행히도 이 문제의 풀이를 미리 알고 푼 팀은 없는 것으로 알고 있다.

문제에서 제약 조건은 단 하나, 두 자동차가 동시에 같은 마을에서 같은 도로를 이동할 수 없다는 것이다. 두 자동차가 동시에 같은 마을에서 같은 도로를 이동하기 위한 필요충분조건은 두 자동차의 시작 마을에서 도착 마을로 가는 최단 거리가 같다는 조건이다. 따라서 자동차의 시작 마을에서 도착 마을로 가는 최단 거리가 서로 다르다면 독립적으로 볼 수 있다.

그렇다면 문제에서 중요한 것은 자동차의 시작 마을에서 도착 마을로 가는 최단 거리가 같은 자동차 집단이다. 이 집단에서 최대한 많은 자동차가 도착 마을로 갈 수 있어야한다. 이는 Ford-Fulkerson 알고리즘으로 구할 수 있다. Ford-Fulkerson 알고리즘을 위해 전체 그래프에서 유효한 간선을 정의해야한다. 유효한 간선이란, 임의의 마을에서 도착 마을로 가는 최단 경로에 포함되는 간선을 의미한다. 이 때 유효한 간선은 당연히 방향성을 갖는다. 이 방향성을 갖는 간선들로 이루어진 그래프에서 Ford-Fulkerson 알고리즘을 통해 최단 거리가 같은 자동차 집단에서 도착 마을로 가는 자동차의 최대 개수를 구할 수 있다.

#include <stdio.h> #include <queue> #include <vector> #include <algorithm> using namespace std; #define MAXN 25004 #define MAXM 50004 #define mp make_pair #define pb push_back #define sz(v) ((int)(v).size()) #define all(v) (v).begin(),(v).end() typedef long long lld; typedef pair<lld, int> pli; int T, N, M, K; lld dist[MAXN]; bool valid[MAXM], swapped[MAXM]; int from[MAXM], to[MAXM]; bool V[MAXN]; vector <int> con[MAXN], conv[MAXN], conn[MAXN], path, pathm; void dijkstra() { int i, j, k; priority_queue <pli> que; for (i=2;i<=N;i++) dist[i] = 3e9; que.push(mp(0, 1)); while (!que.empty()){ lld d = -que.top().first; int q = que.top().second; que.pop(); if (dist[q] != d) continue; for (i=sz(con[q]);i--;){ int k = con[q][i], v = conv[q][i], m = conn[q][i]; if (dist[k] > dist[q]+v) dist[k] = dist[q]+v, que.push(mp(-dist[k], k)); } } for (i=1;i<=M;i++) swapped[i] = valid[i] = to[i] = 0; for (i=2;i<=N;i++){ for (j=sz(con[i]);j--;){ int k = con[i][j], v = conv[i][j], m = conn[i][j]; if (dist[k]+v == dist[i]){ valid[m] = 1; to[m] = k; from[m] = i; } } } } bool cmp(const int &a, const int &b){ return dist[a] < dist[b]; } void reset() { int i; for (i=1;i<=M;i++) if (swapped[i]) swap(from[i], to[i]), swapped[i] = 0; } bool dfs(int n) { int i; V[n] = 1; path.pb(n); if (n == 1) return 1; for (i=sz(con[n]);i--;){ int k = con[n][i], v = conv[n][i], m = conn[n][i]; if (!V[k] && valid[m] && to[m] == k){ pathm.pb(m); if (dfs(k)) return 1; pathm.pop_back(); } } path.pop_back(); return 0; } int main() { int i, j, k, t; for (scanf("%d", &T);T--;){ scanf("%d%d%d", &N, &M, &K); for (i=1;i<=N;i++){ con[i].clear(); conv[i].clear(); conn[i].clear(); } for (i=1;i<=M;i++){ scanf("%d%d%d", &j, &k, &t); con[j].pb(k); conv[j].pb(t); conn[j].pb(i); con[k].pb(j); conv[k].pb(t); conn[k].pb(i); } dijkstra(); vector <int> arr; for (i=1;i<=K;i++){ scanf("%d", &k); arr.pb(k); } sort(all(arr), cmp); int ans = 0; for (i=0;i<K;i++){ if (!i || dist[arr[i-1]] != dist[arr[i]]) reset(); for (j=1;j<=N;j++) V[j] = 0; if (dfs(arr[i])){ ans++; for (j=sz(pathm);j--;){ int m = pathm[j]; swap(to[m], from[m]); swapped[m] ^= 1; } pathm.clear(); path.clear(); } } printf("%d\n", ans); } }