本文共 3500 字，大约阅读时间需要 11 分钟。
为了解决这个问题，我们需要找到一种方法来分配每头牛到一个挤奶机，使得最远走的那头牛的总行走距离最小。这个问题可以通过计算每头牛到每个挤奶机的最短距离，并使用最大流算法来确定最优分配方案。
#include#include #include #include using namespace std;struct Edge { int to, rev; int capacity;};vector > graph; void add_edge(int u, int v, int cap) { Edge e = {v, graph[v].size(), cap}; Edge r = {u, graph[u].size(), 0}; graph[u].push_back(e); graph[v].push_back(r); } int bfs(int s, int t) { vector dist(s + 1, -1); queue q; dist[s] = 0; q.push(s); while (!q.empty()) { int u = q.front(); q.pop(); for (const auto& e : graph[u]) { if (e.capacity > 0 && dist[e.to] == -1) { dist[e.to] = dist[u] + 1; q.push(e.to); } } } return dist[t] != -1; } int dfs(int u, int t, int flow) { if (u == t) return flow; vector ptr(u + 1, 0); for (int i = 0; i < graph[u].size(); ++i) { if (graph[u][i].capacity > 0 && dist[u][i] != -1) { if (ptr[i] == 0) { ptr[i] = graph[u][i].capacity; int min_flow = min(flow, graph[u][i].capacity); int res = dfs(graph[u][i].to, t, min_flow); if (res > 0) { graph[u][i].capacity -= res; graph[graph[u][i].to][graph[u][i].rev].capacity += res; return res; } } } } return 0; } int max_flow(int s, int t) { int flow = 0; vector dist(s + 1, -1); while (bfs(s, t)) { vector ptr(s + 1, 0); int f = 0; do { f = dfs(s, t, INT_MAX); for (int i = 1; i <= s; ++i) { if (graph[i][0].capacity > 0 && ptr[i] == 0) { ptr[i] = graph[i][0].capacity; } } } while (f > 0); flow += f; } return flow; } int main() { int K, C, M; cin >> K >> C >> M; int total_nodes = K + C; int dist[total_nodes + 1][total_nodes + 1]; for (int i = 1; i <= total_nodes; ++i) { for (int j = 1; j <= total_nodes; ++j) { dist[i][j] = 0; } } int current_node = 0; int current_row = 1; while (true) { string line; if (cin >> line) { size_t len = line.size(); int add = min(len, total_nodes - current_node + 1); for (int i = 0; i < add; ++i) { int val = line[i] - ' '; dist[current_row][current_node] = val; current_node++; if (current_node > total_nodes) { break; } } current_row++; if (current_node > total_nodes) { break; } } else { break; } } for (int i = 1; i <= total_nodes; ++i) { for (int j = 1; j <= total_nodes; ++j) { if (dist[i][j] == 0 && i != j) { dist[i][j] = 0; } } } for (int k = 1; k <= total_nodes; ++k) { for (int i = 1; i <= total_nodes; ++i) { for (int j = 1; j <= total_nodes; ++j) { if (dist[i][k] + dist[k][j] < dist[i][j]) { dist[i][j] = dist[i][k] + dist[k][j]; } } } } int S = 0; int T = total_nodes + 1; int max_distance = 0; for (int i = 1; i <= C; ++i) { for (int j = C + 1; j <= total_nodes; ++j) { if (dist[i][j] > max_distance) { max_distance = dist[i][j]; } } } int l = 0, r = max_distance, ans = max_distance; while (l <= r) { int mid = (l + r) / 2; int size = total_nodes + 2; graph.resize(size, vector ()); for (int i = 1; i <= C; ++i) { add_edge(S, i, 1); } for (int i = 1; i <= C; ++i) { for (int j = C + 1; j <= total_nodes; ++j) { if (dist[i][j] <= mid) { add_edge(i, j, 1); } } } for (int j = C + 1; j <= total_nodes; ++j) { add_edge(j, T, M); } int flow = max_flow(S, T); if (flow == C) { ans = mid; r = mid - 1; } else { l = mid + 1; } } cout << ans << endl; }
转载地址：http://wyxfk.baihongyu.com/