Poj 2060 Java 解题报告-最小路径覆盖

Description

Running a taxi station is not all that simple. Apart from the obvious demand for a centralised coordination of the cabs in order to pick up the customers calling to get a cab as soon as possible,there is also a need to schedule all the taxi rides which have been booked in advance.Given a list of all booked taxi rides for the next day, you want to minimise the number of cabs needed to carry out all of the rides.
For the sake of simplicity, we model a city as a rectangular grid. An address in the city is denoted by two integers: the street and avenue number. The time needed to get from the address a, b to c, d by taxi is |a – c| + |b – d| minutes. A cab may carry out a booked ride if it is its first ride of the day, or if it can get to the source address of the new ride from its latest,at least one minute before the new ride’s scheduled departure. Note that some rides may end after midnight.

Input

On the first line of the input is a single positive integer N, telling the number of test scenarios to follow. Each scenario begins with a line containing an integer M, 0 < M < 500, being the number of booked taxi rides. The following M lines contain the rides. Each ride is described by a departure time on the format hh:mm (ranging from 00:00 to 23:59), two integers a b that are the coordinates of the source address and two integers c d that are the coordinates of the destination address. All coordinates are at least 0 and strictly smaller than 200. The booked rides in each scenario are sorted in order of increasing departure time.

Output

For each scenario, output one line containing the minimum number of cabs required to carry out all the booked taxi rides.

Sample Input

2

2

08:00 10 11 9 16

08:07 9 16 10 11

2

08:00 10 11 9 16

08:06 9 16 10 11

题意：

有一些出租车，分别要从一个地方去往另一个地方载客，从一个地方驶向另一个地方的时间为这两个地方的行坐标之差的绝对值+列坐标之差的绝对值（|a-c|+|b-d|），如果一个出租车从一个地方达到另一个地方然后驶向另一个起点时间足够的话，可以取代另一个出租车，这样就可以少用一个出租车，题目求的是最多可以少用几辆出租车。

给定测试数据组数，每组给定出租车数量，然后是每个出租车的出发时间，起点坐标，终点坐标。

思路：

我们把每个乘客的旅程看成一个点，那么如果去搭载第 i 个人的车在把第 i 个人送到目的地后，立即启程去第 j 个人的出发点，并且能在第 j 个人的出发时间前赶到，那么这两个人就只需要一辆车就可以满足需要，于是把每个点拆成两个点，一个代表起点，一个代表终点。我们就在点 i 和 点 j 之间建边就好，对应在二分图中的一条匹配边，依次类推，枚举每两个人的旅途，依次判断然后建边，最后求出最大二分匹配，再根据

最小路径覆盖 = 节点数 – 最大二分匹配

即可得到结果。

原理：

最小路径覆盖问题：用尽量少的不相交简单路径覆盖有向无环图的所有顶点。

对于路径覆盖中的每条连接两个顶点之间的每条有向边pi->pj，我们可以在匹配图中对应做一条连接pi’与pj”的边，这样做出来图的就是一个匹配图。

原图的路径覆盖和新图的匹配间有对应关系：

v 路径要求不能相交，恰好对应于匹配中两匹配边不能有公共端点。

PS:（如果得到的图不是一个匹配图，那么这个图中必定存在这样两条边 pi’—pj” 及 pi’ —-pk”，（j!=k），那么在路径覆盖图中就存在了两条边pi–>pj, pi—>pk ，那边从pi出发的路径就不止一条了，这与路径覆盖图是矛盾的；还有另外一种情况就是存在pi’—pj”,pk’—pj”，这种情况也类似可证）

（1）：于是求最大匹配后，每条覆盖边都是匹配中的一条边，不能被匹配上的点，即是路径的最后一个点。有多少个不能被匹配的点，就有多少条路径存在。

（2）：如果匹配数为零，那么不存在有向边，于是显然有最小路径覆盖=节点数；如果在P’中增加一条匹配边pi’->pj”，那么在图P的路径覆盖中就存在一条由pi连接pj的边，也就是说pi与pj 在一条路径上，于是路径覆盖数就可以减少一个； 如此继续增加匹配边，每增加一条，路径覆盖数就减少一条；直到匹配边不能继续增加时，路径覆盖数也不能再减少了，此时就有了前面的公式。

路径数=原点数－匹配边数。因此我们使匹配边数最大，即是使路径数最小。

最初源代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
import java.util.Arrays;
import java.util.Scanner;

public class Main{
    static int n = 0;//提前预定的taxi总数
    static final int MAX = 500;//最大容量
    static Booked[] booked = new Booked[MAX];//taxi对象数组
    static boolean[][] graph = new boolean[MAX * 2][MAX * 2];//建图
    static boolean[] visit = new boolean[MAX * 2];//访问标记
    static int[] link = new int[MAX * 2];//记录前节点
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        int t = cin.nextInt();
        while (t-- != 0) {
            n = cin.nextInt();
            for (int i = 0; i < n; i++) {
                String[] ss = cin.next().split(":");
                int time = Integer.parseInt(ss[0]) * 60 + Integer.parseInt(ss[1]);//计算出发时间
                booked[i] = new Booked(time, cin.nextInt(), cin.nextInt(), cin.nextInt(), cin.nextInt());//读入起始坐标
            }
            init();
            System.out.println(n - hungray());//节点数 - 最大二分匹配
        }
    }
    static void init() {//构建图
        for (int i = 0; i < MAX * 2; i++)
            Arrays.fill(graph[i], false);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (booked[i].reachable(booked[j]))
                    graph[i][j + n] = true;
            }
        }
    }
    static boolean find(int x) {//寻找可增广路
        for (int i = 0; i < n * 2; i++) {
            if (graph[x][i] && !visit[i]) {
                visit[i] = true;
                if (link[i] == -1 || find(link[i])) {
                    link[i] = x;
                    return true;
                }
            }
        }
        return false;
    }
    static int hungray() {//匈牙利求最大匹配
        int ans = 0;
        Arrays.fill(link, -1);
        for (int i = 0; i < n; i++) {
            Arrays.fill(visit, false);
            if (find(i))
                ans++;
        }
        return ans;
    }
}
class Booked {//被预定的taxi类
    int time, a, b, c, d;
    public Booked(int time, int a, int b, int c, int d) {
        this.time = time;//出发时间
        this.a = a;//起点坐标
        this.b = b;
        this.c = c;//终点坐标
        this.d = d;
    }
    boolean reachable(Booked bo) {//两条路线能否用一辆taxi来代替
        return this.time + Math.abs(this.a - this.c) + Math.abs(this.b - this.d) + Math.abs(bo.a - this.c) + Math.abs(bo.b - this.d) < bo.time;
    }
}

针对此题的优化代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main{
    static int n = 0;
    static final int MAX = 505;
    static Booked[] booked = new Booked[MAX];
    static boolean[][] graph = new boolean[MAX][MAX];
    static boolean[] visit = new boolean[MAX];
    static int[] link = new int[MAX];
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int Case = Integer.parseInt(br.readLine());
        while (Case-- != 0) {
            n = Integer.parseInt(br.readLine());
            for (int i = 1; i <= n; i++) {
                String[] ss = br.readLine().split(" ");
                int time = Integer.parseInt(ss[0].substring(0, 2)) * 60 + Integer.parseInt(ss[0].substring(3));
                booked[i] = new Booked(time, Integer.parseInt(ss[1]), Integer.parseInt(ss[2]), Integer.parseInt(ss[3]), Integer.parseInt(ss[4]));
            }
            init();
            System.out.println(n - hungray());
        }
    }
    static void init() {
        for (int i = 0; i < MAX; i++)
            Arrays.fill(graph[i], false);
        for (int i = 1; i <= n; i++) {
            for (int j = i + 1; j <= n; j++) {
                if (booked[i].reachable(booked[j]))
                    graph[i][j] = true;
            }
        }
    }
    static boolean find(int x) {
        for (int i = x + 1; i <= n; i++) {
            if (graph[x][i] && !visit[i]) {
                visit[i] = true;
                if (link[i] == -1 || find(link[i])) {
                    link[i] = x;
                    return true;
                }
            }
        }
        return false;
    }
    static int hungray() {
        int ans = 0;
        Arrays.fill(link, -1);
        for (int i = 1; i <= n; i++) {
            Arrays.fill(visit, false);
            if (find(i))
                ans++;
        }
        return ans;
    }
}
class Booked {
    int time, a, b, c, d;
    public Booked(int time, int a, int b, int c, int d) {
        this.time = time;
        this.a = a;
        this.b = b;
        this.c = c;
        this.d = d;
    }
    boolean reachable(Booked bo) {
        return this.time + Math.abs(this.a - this.c) + Math.abs(this.b - this.d) + Math.abs(bo.a - this.c) + Math.abs(bo.b - this.d) < bo.time;
    }
}

除非注明，饮水思源博客文章均为原创，转载请以链接形式标明本文地址

本文地址： http://www.alonemonkey.com/acmpoj2060.html

本文链接：http://www.alonemonkey.com/acmpoj2060.html