Repairing Company

题目描述

Lily runs a repairing company that services the $Q$ blocks in the city. One day the company receives $M$ repair tasks, the $i$-th of which occurs in block $p_i$, has a deadline $t_i$ on any repairman’s arrival, which is also its starting time, and takes a single repairman $d_i$ time to finish. Repairmen work alone on all tasks and must finish one task before moving on to another. With a map of the city in hand, Lily want to know the minimum number of repairmen that have to be assign to this day’s tasks.

题意概述

有$Q$个街道和$M$个任务。给出两两街道之间的距离以及每个任务的地点$p_i$、开始时间$t_i$和花费时间$d_i$。问至少需要多少个工人才能完成所有任务。工人开始时可以在任意街道，一个工人只能同时做一个任务。

数据范围：$1 \le Q \le 20, \ 1 \le M \le 200$。

算法分析

首先用 Floyd 求出任意两点之间的距离，用$dist_{i, j}$表示。对于两个任务$i, j$，若$t_i+d_i+dist_{p_i, p_j} \le t_j$，那么做第$i$个任务的工人可以继续做第$j$个任务。显然，任务之间构成了一张有向无环图，问题转化为最小覆盖问题。将图中每个点$u$拆成$u_0, u_1$两个点。若原图中有一条边$(u, v)$，则在新图中连边$(u_0, v_1)$。答案就是$M$减去新图的最大匹配数。

代码

#include <cstdio>
#include <cstring>

int min(int a, int b) {
  return a < b ? a : b;
}

static const int Q = 25;
static const int M = 405;
int mp[Q][Q], p[M], t[M], d[M];
int nume, h[M];
struct Edge {
  int v, f, nxt;
} e[M * M << 1];

void add_edge(int u, int v, int f) {
  e[++ nume] = (Edge) { v, f, h[u] }, h[u] = nume;
  e[++ nume] = (Edge) { u, 0, h[v] }, h[v] = nume;
}

namespace flow {
  int S, T, g[M], dist[M], que[M], gap[M];

  bool bfs() {
    memcpy(g, h, sizeof h);
    memset(dist, 0x3f, sizeof dist), memset(gap, 0, sizeof gap);
    int qb = 0, qe = 1; dist[T] = 0, que[0] = T, ++ gap[0];
    while (qb < qe) {
      int u = que[qb ++];
      for (int i = g[u]; i; i = e[i].nxt)
        if (e[i ^ 1].f && dist[e[i].v] > dist[u] + 1)
          dist[e[i].v] = dist[u] + 1, que[qe ++] = e[i].v, ++ gap[dist[e[i].v]];
    }
    return dist[S] < 1e9;
  }

  int dfs(int t, int low) {
    if (t == T) return low;
    int used = 0;
    for (int &i = g[t]; i; i = e[i].nxt)
      if (e[i].f && dist[e[i].v] == dist[t] - 1) {
        int flow = dfs(e[i].v, min(e[i].f, low - used));
        if (flow) e[i].f -= flow, e[i ^ 1].f += flow, used += flow;
        if (used == low || dist[S] > T) return used;
      }
    if (! -- gap[dist[t]]) dist[S] = T + 1;
    else ++ gap[++ dist[t]], g[t] = h[t];
    return used;
  }

  int maxflow() {
    bfs(); int flow = 0;
    while (dist[S] <= T) flow += dfs(S, 1e9);
    return flow;
  }
}

int main() {
  int q, m;
  while (scanf("%d%d", &q, &m), q) {
    nume = 1, memset(h, 0, sizeof h);
    flow :: S = m << 1, flow :: T = (m << 1) + 1;
    for (int i = 0; i < q; ++ i)
      for (int j = 0; j < q; ++ j) scanf("%d", &mp[i][j]);
    for (int i = 0; i < q; ++ i)
      for (int j = 0; j < q; ++ j) if (! ~ mp[i][j]) mp[i][j] = 1e9;
    for (int k = 0; k < q; ++ k)
      for (int i = 0; i < q; ++ i)
        for (int j = 0; j < q; ++ j) mp[i][j] = min(mp[i][j], mp[i][k] + mp[k][j]);
    for (int i = 0; i < m; ++ i) scanf("%d%d%d", &p[i], &t[i], &d[i]), -- p[i];
    for (int i = 0; i < m; ++ i)
      for (int j = 0; j < m; ++ j) if (i != j && t[i] + d[i] + mp[p[i]][p[j]] <= t[j]) add_edge(i, j + m, 1);
    for (int i = 0; i < m; ++ i) add_edge(flow :: S, i, 1), add_edge(i + m, flow :: T, 1);
    printf("%d\n", m - flow :: maxflow());
  }
  return 0;
}