二分图与网络流

二分图

[EOJ] - 1864

这道题用二分图的匈牙利算法

不存在难处

关键是:如何把问题抽象成二分图

显然

对于每一个word来说都是相互独立的

word之间相互不影响

于是

word的第i个字符如果出现在第j个cube中

可以认为i和j是连通的

由此可以得到lineExist数组

下面就是一个二分图的dfs(下详)

public class Main {

    private static boolean[] visited; // 这个点是不是被访问过
    private static int numberOfCube; // cube的个数
    private static boolean[][] lineExist; // word的第i个字符是不是出现在第j个cube中
    private static int[] match; // 是不是能找到这样一条路径配对

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextInt()) {
            numberOfCube = in.nextInt();
            int numberOfWord = in.nextInt();
            String[] cube = new String[numberOfCube];
            visited = new boolean[numberOfCube];
            match = new int[numberOfCube];
            ArrayList<Integer> list = new ArrayList<Integer>(); // 存放哪几个word是可以用cube拼出来的
            for (int i = 0; i < numberOfCube; ++i) {
                cube[i] = in.next();
            }
            for (int i = 0; i < numberOfWord; ++i) {
                String word = in.next();
                lineExist = new boolean[word.length()][numberOfCube];
                // 遍历word的每一个字符,如果第j个字符出现在第k个cube,就认为他们是连通的
                for (int j = 0; j < word.length(); ++j) {
                    for (int k = 0; k < numberOfCube; ++k) {
                        if (cube[k].indexOf(word.charAt(j)) != -1) {
                            lineExist[j][k] = true;
                        }
                    }
                }
                boolean matched = true;
                Arrays.fill(match, -1);

                // 对word的每一个字符,开始找
                for (int j = 0; j < word.length(); ++j) {
                    Arrays.fill(visited, false);
                    // 如果某个字符不能找到配对,就可以不用往下了,已经不可能拼成了
                    if (!dfs(j)) {
                        matched = false;
                        break;
                    }
                }
                if (matched) {
                    list.add(i);
                }
            }
            if (list.isEmpty()) {
                System.out.println(-1);
            } else {
                for (int i = 0; i < list.size(); ++i) {
                    System.out.print(list.get(i));
                    System.out.print(i == list.size() - 1 ? "\n" : " ");
                }
            }
        }

    }

    /**
     * 二分图的匈牙利算法
     * 
     * @param from
     *            起点
     * @return 如果能找到,返回true,否则,false
     */
    private static boolean dfs(int from) {
        // 遍历所有的cube
        for (int to = 0; to < numberOfCube; ++to) {
            // 如果连通,并且没有被访问过
            if (lineExist[from][to] && !visited[to]) {
                visited[to] = true;
                // 如果还没有配对过,或者能够给他腾出一个新的配对
                if (match[to] == -1 || dfs(match[to])) {
                    match[to] = from;
                    return true;
                }
            }
        }
        return false;
    }

}

[EOJ] - 2069

这道题和上课的一题猎人打鸟的例题是很像的

要把问题抽象成二分图

如果说(R,C)存在一个小行星

就认为R和C是连通的

于是

在所有小行星的坐标确定以后

就可以得到一个图

下面就是用匈牙利算法求增广路径

遍历size的Row(或者Column,一样的)

对于每一个遍历都去做DFS

如果return的是true说明找到一条路径

于是计数器加1表示要消耗一个炮弹

如果是false就继续

最后计数器的结果就是答案

public class Main {

    private static boolean[] visited; // 这个点是不是被访问过
    private static int size; // N*N的大小
    private static boolean[][] asteroidInRowAndColumn; // 某行某列是不是有一个小行星
    private static int[] match; // 是不是能找到这样一条路径配对

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextInt()) {
            size = in.nextInt();
            int numberOfAsteroid = in.nextInt();
            // 注意小行星的编号是从1~N,不是0~N-1
            visited = new boolean[size + 1];
            match = new int[size + 1];
            asteroidInRowAndColumn = new boolean[size + 1][size + 1];
            // 读入小行星的坐标,并且标记row和column是相互连通的
            for (int i = 0; i < numberOfAsteroid; ++i) {
                int row = in.nextInt();
                int column = in.nextInt();
                asteroidInRowAndColumn[row][column] = true;
            }
            // 同样,match的重置在循坏外
            Arrays.fill(match, -1);
            int weaponUsed = 0; // 使用的武器数
            for (int j = 1; j <= size; ++j) {
                // visited的重置在循环内
                Arrays.fill(visited, false);
                if (dfs(j)) {
                    ++weaponUsed; // 如果能找到,就在这里放武器,就加1
                }

            }
            System.out.println(weaponUsed);
        }

    }

    /**
     * 二分图的匈牙利算法
     * 
     * @param from
     *            起点
     * @return 如果能找到,返回true,否则,false
     */
    private static boolean dfs(int from) {
        for (int to = 1; to <= size; ++to) {
            // 如果连通,并且没有被访问过
            if (asteroidInRowAndColumn[from][to] && !visited[to]) {
                visited[to] = true;
                // 如果还没有配对过,或者能够给他腾出一个新的配对
                if (match[to] == -1 || dfs(match[to])) {
                    match[to] = from;
                    return true;
                }
            }
        }
        return false;
    }

}

网络流

/**
     * 广度优先搜索,判断是不是还存在增广路径
     * 
     * @param sourcePoint
     *            源点
     * @param terminalPoint
     *            终点
     * @return 如果存在增广路径,返回true,否则,false
     */
    static boolean bfs(int sourcePoint, int terminalPoint) {
        Queue<Integer> queue = new LinkedList<Integer>(); 
        previousPoint = new int[numberOfIntersectionsPoints + 1];
        boolean[] visited = new boolean[numberOfIntersectionsPoints + 1]; 
        // 定义源点是从源点来的,记录访问,并入队
        previousPoint[sourcePoint] = sourcePoint;
        visited[sourcePoint] = true;
        queue.add(sourcePoint);

        while (!queue.isEmpty()) {
            int from = queue.poll();

            for (int to = 1; to <= numberOfIntersectionsPoints; ++to) {

                if (flow[from][to] > 0 && !visited[to]) {
                    previousPoint[to] = from;
                    visited[to] = true;
                    if (to == terminalPoint) {
                        return true; // 如果到达终点,说明存在增广路径,true
                    }
                    queue.add(to); 
                }
            }
        }
        return false; // 不存在增广路径了
    }   
/**
     * 计算最大流
     * 
     * @param sourcePoint
     *            源点
     * @param terminalPoint
     *            终点
     * @return 从源点到终点的最大流
     */
    static int maxFlow(int sourcePoint, int terminalPoint) {
        int maxFlow = 0; // 最大流
        int delta = 0; // 增量
        while (bfs(sourcePoint, terminalPoint)) {
            delta = Integer.MAX_VALUE; 
            int to = terminalPoint; // 从终点倒着走
            // 还没有走到源点的时候,不断取出previousPoint为from,取flow[from][to]与delta较小的,由此求得最小的增量
            while (to != sourcePoint) {
                int from = previousPoint[to];
                delta = Math.min(delta, flow[from][to]);
                to = from;
            }
            // 继续从终点倒着走
            to = terminalPoint;
            // 还没有走到源点的时候,求出全部的反向边
            while (to != sourcePoint) {
                int from = previousPoint[to];
                // 取出from,维护[from][to]和[to][from]
                flow[from][to] -= delta;
                flow[to][from] += delta;
                to = from;
            }

            maxFlow += delta;
        }
        return maxFlow;
    }

[HDU] - 1532

public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextInt()) {

            int numberOfDitches = in.nextInt();
            numberOfIntersectionsPoints = in.nextInt();
            flow = new int[numberOfIntersectionsPoints + 1][numberOfIntersectionsPoints + 1];
            while (numberOfDitches-- != 0) {
                int from = in.nextInt();
                int to = in.nextInt();
                int traffic = in.nextInt();
                flow[from][to] += traffic;
            }
            final int SOURCE_POINT = 1;
            final int TERMINAL_POINT = numberOfIntersectionsPoints;
            System.out.println(maxFlow(SOURCE_POINT, TERMINAL_POINT));
        }
    }

[HDU] - 3549

public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int caseNumber = in.nextInt();
        for (int caseIndex = 1; caseIndex <= caseNumber; ++caseIndex) {

            numberOfVertexes = in.nextInt();
            int numberOfEdges = in.nextInt();
            flow = new int[numberOfVertexes + 1][numberOfVertexes + 1];
            while (numberOfEdges-- != 0) {
                int from = in.nextInt();
                int to = in.nextInt();
                int traffic = in.nextInt();
                flow[from][to] += traffic;
            }

            final int SOURCE_POINT = 1;
            final int TERMINAL_POINT = numberOfVertexes;
            System.out.println("Case " + caseIndex + ": " + maxFlow(SOURCE_POINT, TERMINAL_POINT));
        }
    }