[Medium] SlimeXGrandSlimeAuto
Topcoder SRM 506 Div1
district[i] -> district[i+1] 의 경로를 생각해보자
이렇게 이동하는 도중에 차를 탄다고 결정했다면
district[i]에서 출발하여 걸어서 차가 위치한 도시 아무데나 간 다음
그 차를 타고 바로 district[i+1] 까지 가는 것이 최적이다
다른 짓을 하거나 차를 두 번 이상 타는 것은 무조건 손해다.
따라서 차 하나는 district[i] -> district[i+1] 인 경로 중 하나에 기여할 수 있고, 그 기여분을 계산할 수 있다.
이제 각 차들이 어느 경로에 기여할 지를 결정해서 기여분의 합을 최대로 만들어야한다. 이것은 바로 이분가중매칭 이다!
MCMF나 헝가리안메소드를 쓰면 된다.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include <cctype> | |
| #include <vector> | |
| #include <queue> | |
| #include <algorithm> | |
| using namespace std; | |
| struct MinCostFlow { | |
| typedef int cap_t; | |
| typedef int cost_t; | |
| bool iszerocap(cap_t cap) { return cap == 0; } | |
| struct edge { | |
| int target; | |
| cost_t cost; | |
| cap_t residual_capacity; | |
| size_t revid; | |
| }; | |
| int n; | |
| vector<vector<edge>> graph; | |
| MinCostFlow(int n) : n(n), graph(n) {} | |
| void addEdge(int s, int e, cost_t cost, cap_t cap) { | |
| if (s == e) return; | |
| edge forward = { e, cost, cap, graph[e].size() }; | |
| edge backward = { s, -cost, 0, graph[s].size() }; | |
| graph[s].emplace_back(forward); | |
| graph[e].emplace_back(backward); | |
| } | |
| pair<cost_t, cap_t> AugmentShortest(int s, int e, cap_t flow_limit) { | |
| auto infinite_cost = numeric_limits<cost_t>::max() / 2; | |
| auto infinite_flow = numeric_limits<cap_t>::max(); | |
| queue<int> q; | |
| vector<pair<cost_t, cap_t>> dist(n, { infinite_cost, 0 }); | |
| vector<bool> inqueue(n); | |
| vector<int> from(n, -1); | |
| dist[s] = { 0, infinite_flow }; | |
| inqueue[s] = true; | |
| q.push(s); | |
| while (!q.empty()) { | |
| int u = q.front(); | |
| q.pop(); | |
| inqueue[u] = false; | |
| for (auto& e : graph[u]) { | |
| if (iszerocap(e.residual_capacity)) continue; | |
| auto ncost = dist[u].first + e.cost; | |
| auto nflow = min(dist[u].second, e.residual_capacity); | |
| if (dist[e.target].first <= ncost) continue; | |
| dist[e.target] = { ncost, nflow }; | |
| from[e.target] = e.revid; | |
| if (!inqueue[e.target]) { | |
| q.push(e.target); | |
| inqueue[e.target] = true; | |
| } | |
| } | |
| } | |
| auto p = e; | |
| auto pathcost = dist[p].first; | |
| auto flow = dist[p].second; | |
| if (iszerocap(flow) || (flow_limit <= 0 && pathcost >= 0)) return { 0, 0 }; | |
| if (flow_limit > 0) flow = min(flow, flow_limit); | |
| while (from[p] != -1) { | |
| auto nedge = from[p]; | |
| auto np = graph[p][nedge].target; | |
| auto fedge = graph[p][nedge].revid; | |
| graph[p][nedge].residual_capacity += flow; | |
| graph[np][fedge].residual_capacity -= flow; | |
| p = np; | |
| } | |
| return { pathcost * flow, flow }; | |
| } | |
| pair<cost_t, cap_t> solve(int s, int e, cap_t flow_minimum = numeric_limits<cap_t>::max()) { | |
| cost_t total_cost = 0; | |
| cap_t total_flow = 0; | |
| for (;;) { | |
| auto res = AugmentShortest(s, e, flow_minimum - total_flow); | |
| if (res.second <= 0) break; | |
| total_cost += res.first; | |
| total_flow += res.second; | |
| } | |
| return { total_cost, total_flow }; | |
| } | |
| }; | |
| const int INF = 100000000; | |
| inline int conv(char c) { | |
| if (isdigit(c)) { | |
| return c - '0' + 1; | |
| } | |
| else if (islower(c)) { | |
| return c - 'a' + 11; | |
| } | |
| else if (isupper(c)) { | |
| return c - 'A' + 37; | |
| } | |
| else { | |
| return INF; | |
| } | |
| } | |
| class SlimeXGrandSlimeAuto { | |
| public: | |
| int travel(vector<int> cars, vector<int> districts, vector<string> roads, int inverseWalkSpeed, int inverseDriveSpeed) { | |
| int n = roads.size(), m1 = districts.size(), m2 = cars.size(); | |
| vector<vector<int>> w(n, vector<int>(n, INF)); | |
| for (int i = 0; i < n; ++i) { | |
| for (int j = 0; j < n; ++j) { | |
| w[i][j] = conv(roads[i][j]); | |
| } | |
| w[i][i] = 0; | |
| } | |
| for (int k = 0; k < n; ++k) { | |
| for (int i = 0; i < n; ++i) { | |
| for (int j = 0; j < n; ++j) { | |
| w[i][j] = min(w[i][j], w[i][k] + w[k][j]); | |
| } | |
| } | |
| } | |
| MinCostFlow mcf(m1 + m2 + 2); | |
| for (int j = 0; j < m2; ++j) { | |
| mcf.addEdge(0, 1 + j, 0, 1); | |
| } | |
| int ans = 0; | |
| for (int i = 0; i < m1; ++i) { | |
| mcf.addEdge(1 + m2 + i, 1 + m2 + m1, 0, 1); | |
| int u = (i > 0) ? districts[i - 1] : 0; | |
| int v = districts[i]; | |
| ans += w[u][v] * inverseWalkSpeed; | |
| for (int j = 0; j < m2; ++j) { | |
| int oldval = w[u][v] * inverseWalkSpeed; | |
| int newval = w[u][cars[j]] * inverseWalkSpeed + w[cars[j]][v] * inverseDriveSpeed; | |
| int diff = min(0, newval - oldval); | |
| mcf.addEdge(1 + j, 1 + m2 + i, diff, 1); | |
| } | |
| } | |
| return ans + mcf.solve(0, 1 + m2 + m1).first; | |
| } | |
| }; |