最小路径覆盖,关键问题在于模型的抽象。题目描述中给的是用最小的出租车数量载走所有的乘客,一看见这个问题,我们就可以想到最小覆盖,这里把乘客看做顶点、出租车看做路径,即用最小的路径数覆盖所有的顶点。拆点之后,我们可以将所有满足条件的两个点连一条单向边。由于满足后继性质,所以没有匹配的顶点一定是路径终点,即代表一条路径。所以最小路径覆盖就求解出来啦。
CODE:
#include <iostream> #include <cstdlib> #include <cstring> #include <cstdio> #include <map> #include <cmath> using namespace std; const int MAXN = 510; struct node { int costM; int tot; int x1, y1, x2, y2; }a[MAXN]; int G[MAXN][MAXN]; int xlink[MAXN], ylink[MAXN]; bool vis[MAXN]; int nx, ny; void init() { memset(G, 0, sizeof(G)); memset(xlink, -1, sizeof(xlink)); memset(ylink, -1, sizeof(ylink)); } bool ED(int u) { for(int v = 1; v <= ny; v++) if(G[u][v]) { if(!vis[v]) { vis[v] = 1; if(ylink[v] == -1 || ED(ylink[v])) { xlink[u] = v; ylink[v] = u; return true; } } } return false; } void solve() { int ans = 0; for(int i = 1; i <= nx; i++) { if(xlink[i] == -1) { memset(vis, 0, sizeof(vis)); ans += ED(i); } } printf("%d\n", nx-ans); } void read_case() { init(); scanf("%d", &nx); ny = nx; for(int i = 1; i <= nx; i++) { int h, min, x1, y1, x2, y2; scanf("%d:%d %d %d %d %d", &h, &min, &a[i].x1, &a[i].y1, &a[i].x2, &a[i].y2); a[i].costM = h*60 + min; a[i].tot = a[i].costM + abs(a[i].x1-a[i].x2) + abs(a[i].y1-a[i].y2); } for(int i = 1; i < nx; i++) { for(int j = i+1; j <= nx; j++) { int dif = a[j].costM - a[i].tot; int limit = abs(a[j].x1 - a[i].x2) + abs(a[j].y1 - a[i].y2); if(dif > limit) G[i][j] = 1; } } } int main() { int T; scanf("%d", &T); while(T--) { read_case(); solve(); } return 0; }