专栏首页机器学习入门挑战程序竞赛系列(26):3.5二分图匹配(1)

挑战程序竞赛系列(26):3.5二分图匹配(1)

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/u014688145/article/details/75902147

挑战程序竞赛系列(26):3.5二分图匹配(1)

详细代码可以fork下Github上leetcode项目,不定期更新。

练习题如下:

POJ 1274: The perfect Stall

熟悉了最大流,二分图匹配就易如反掌,之所以是个最大流问题,可以想想增广路径是如何分配流量的,传说中的反悔重走在这里运用的淋漓尽致。

步骤: 1. 新建源点s和汇点t 2. 源点s与所有奶牛顶点连接,且边权为1,这样能够保证匹配时不漏掉任何一头牛(每头牛都有机会在自己想要的牛奶棚产奶)。 3. 所有牛奶棚与汇点t连接,边权为1,把所有产生的奶按照一单位运输到最终目的地。(一条流水线) 4. 奶牛与喜爱的牛奶棚建立连接,边权为1,增广路径在此处发挥了极其大的价值,每次找一条增广路径时,可以让已经匹配的边逆流(传说中的返回重来),只要能找到一条,最大匹配数+1。

可以用一般的最大流算法实现:

    class Edge{
        int from;
        int to;
        int cap;
        int rev;
        public Edge(int from, int to, int cap, int rev){
            this.from = from;
            this.to = to;
            this.cap = cap;
            this.rev = rev;
        }
    }

    List<Edge>[] g;
    int V;
    void solve() {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()){
            int N = in.nextInt();
            int M = in.nextInt();
            V = N + M + 2;
            int s = 0, t = N + M + 1;
            g = new ArrayList[V];
            for (int i = 0; i < V; ++i) g[i] = new ArrayList<Edge>();

            for (int i = 1; i <= N; ++i){
                addEdge(s, i, 1);
            }

            for (int j = 1; j <= M; ++j){
                addEdge(j + N, t, 1);
            }

            for (int i = 1; i <= N; ++i){
                int m = in.nextInt();
                for (int j = 0; j < m; ++j){
                    int stall = in.nextInt();
                    addEdge(i, stall + N, 1);
                }
            }
            System.out.println(fordFulkerson(s, t));
        }
        in.close();
    }

    public void addEdge(int from, int to, int cap){
        g[from].add(new Edge(from, to, cap, g[to].size()));
        g[to].add(new Edge(to, from, 0, g[from].size() - 1)); 
    }


    static final int INF = 1 << 30;
    public int fordFulkerson(int s, int t){
        int flow  = 0;
        for (;;){
            int f = dfs(s, t, INF, new boolean[V]);
            if (f > 0) flow += f;
            else break;
        }
        return flow;
    }

    public int dfs(int s, int t, int f, boolean[] visited){ 
        if (s == t) return f;
        visited[s] = true;
        for (Edge e : g[s]){
            int to = e.to;
            if (!visited[to] && e.cap > 0){
                int d = dfs(to, t, Math.min(f, e.cap), visited);
                if (d > 0){
                    e.cap -= d;
                    g[to].get(e.rev).cap += d;
                    return d;
                }
            }
        }
        return 0;
    }

    void run() throws Exception {
        solve();
    }

    public static void main(String[] args) throws Exception {
        new SolutionDay21_P1274().run();
    }

但其实每次找寻增广路径,流量都只会+1,所以只要找到增广路径即可,无需返回流量,简化版的二分图如下:

    List<Integer>[] g;
    int V;
    int N;
    void solve() {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()){
            N = in.nextInt();
            int M = in.nextInt();
            V = N + M;
            g = new ArrayList[V];
            for (int i = 0; i < V; ++i) g[i] = new ArrayList<Integer>();

            for (int i = 0; i < N; ++i){
                int m = in.nextInt();
                for (int j = 0; j < m; ++j){
                    int stall = in.nextInt();
                    addEdge(i, stall + N - 1);
                }
            }

            System.out.println(bipartite_matching());
        }
        in.close();
    }

    public void addEdge(int from, int to){
        g[from].add(to);
        g[to].add(from);
    }

    public int bipartite_matching(){
        int res = 0;
        matching = new int[V];
        Arrays.fill(matching, -1);
        for (int i = 0; i < N; ++i){
            if (matching[i] < 0){
                if (dfs(i, new boolean[V])){
                    res ++;
                }
            }
        }
        return res;
    }

    int[] matching;
    public boolean dfs(int v, boolean[] used){
        used[v] = true;
        for (int u : g[v]){
            int w = matching[u];
            if (w < 0 || !used[w] && dfs(w, used)){
                matching[u] = v;
                matching[v] = u;
                return true;
            }
        }
        return false;
    }

和最大流算法稍微有些区别,用matching来记录匹配时的状态,used来记录是否已经反悔(每人只能反悔一次)。

POJ 2112: Optimal Milking

思路:二分+最大流,先计算所有奶牛到每台机器的最短距离,采用warshall_floyd算法,接着二分猜最长距离的最短距离边,如果猜的值够大,那么所有的奶牛都能找到机器。而如果猜的值较小,那么必然有几头奶牛不能成功找到对应的机器。如何表示是否有奶牛匹配到对应的机器呢?采用二分图匹配,建立源点s和汇点t,如果最终最大流 == 奶牛数,说明当前值可以进一步缩小。

代码如下:

    int[][] graph;
    int V;
    int K;
    int C;
    int M;
    void solve() {
        K = ni();
        C = ni();
        M = ni();
        V = K + C + 2;

        graph = new int[K + C][K + C];
        for (int i = 0; i < K + C; ++i){
            for (int j = 0; j < K + C; ++j){
                int d = ni();
                graph[i][j] = d != 0 ? d : INF;
            }
        }

        int n = K + C;
        for (int k = 0; k < n; ++k){
            for (int i = 0; i < n; ++i){
                for (int j = 0; j < n; ++j){
                    graph[i][j] = Math.min(graph[i][j], graph[i][k] + graph[k][j]);
                }
            }
        }

        int lb = 0, ub = 200 * n;
        while (ub - lb > 1){
            int mid = (ub + lb) / 2;
            if (check(mid)) ub = mid;
            else lb = mid;
        }
        out.println(ub);
    }

    public boolean check(int limit){
        g = new ArrayList[V];
        for (int i = 0; i < V; ++i) g[i] = new ArrayList<Edge>();

        int s = 0;
        int t = V - 1;

        //源点到奶牛
        for (int id = 0; id < C; ++id){
            addEdge(s, id + 1 + K, 1);
        }

        //机器到汇点
        for (int id = 0; id < K; ++id){
            addEdge(id + 1, t, M);
        }

        for (int cow = 0; cow < C; ++cow){
            for (int ml = 0; ml < K; ++ml){
                if (graph[cow + K][ml] <= limit){
                    addEdge(cow + K + 1, ml + 1, 1);
                }
            }
        }

        return maxFlow(s, t) == C;
    }

    public void addEdge(int from, int to, int cap){
        g[from].add(new Edge(from, to, cap, g[to].size()));
        g[to].add(new Edge(to, from, 0, g[from].size() - 1));
    }


    /************dinic************/
    class Edge{
        int from;
        int to;
        int cap;
        int rev;
        public Edge(int from, int to, int cap, int rev){
            this.from = from;
            this.to = to;
            this.cap = cap;
            this.rev = rev;
        }
    }

    static final int INF = 1 << 28;
    List<Edge>[] g;
    public int maxFlow(int s, int t){
        int flow = 0;
        for (;;){
            bfs(s);
            if (level[t] < 0) break;
            int f = 0;
            while ((f = dfs(s, t, INF, new boolean[V])) > 0) flow += f;
        }
        return flow;
    }

    int[] level;
    public void bfs(int s){
        level = new int[V];
        Arrays.fill(level, -1);
        level[s] = 0;
        Queue<Integer> queue = new LinkedList<Integer>();
        queue.offer(s);
        while (!queue.isEmpty()){
            int v = queue.poll();
            for (Edge e : g[v]){
                int to = e.to;
                if (level[to] < 0 && e.cap > 0){
                    level[to] = level[v] + 1;
                    queue.offer(to);
                }
            }
        }
    }

    public int dfs(int s, int t, int f, boolean[] visited){
        if (s == t) return f;
        visited[s] = true;
        for (Edge e : g[s]){
            int to = e.to;
            if (!visited[to] && e.cap > 0 && level[e.from] + 1 == level[to]){
                int d = dfs(to, t, Math.min(f, e.cap), visited);
                if (d > 0){
                    e.cap -= d;
                    g[to].get(e.rev).cap += d;
                    return d;
                }
            }
        }
        return 0;
    }

POJ 1486: Sorting Slides

此题用贪心是错误的,具体思路如下:

每次找到出度或者入度为1的(也就是框上只有一个点,或者点只在一个框上的),把这样的点和框一起删除,在继续找,直到找不出为止。

举个反例:

5
1 4 1 4
2 7 2 7
5 11 5 11
8 13 9 14
9 14 8 13
3 3
3 3
6 6
10 10
12 12

实际输出:
(c,3)

贪心结果为:none

画图就能明白,虽然在此case下,所有的顶点出度都大于1,所以贪心会认为没有确定的边,但是如果你枚举某一条边,你会发现它有一种情况是矛盾的,进而推出了一条唯一确定的边。

此题的思路得反一反,首先明确一点,如果所有边都存在的情况下,必然是完美匹配图,所以不管怎么匹配,最终匹配的结果一定是n,那么当删除一条确定关系的边会发生什么?容易想象,如果删除一条边,导致该二分图不再完美,那么该条边连接的slide和point是确定的,否则可删可不删。

代码如下:

    class Point{
        int x;
        int y;
        public Point(int x, int y){
            this.x = x;
            this.y = y;
        }
    }

    class Slide{
        int minX;
        int maxX;
        int minY;
        int maxY;

        public Slide(int minX, int maxX, int minY, int maxY){
            this.minX = minX;
            this.maxX = maxX;
            this.minY = minY;
            this.maxY = maxY;
        }

        public boolean contain(Point point){
            int x = point.x;
            int y = point.y;
            return minX < x && x < maxX && minY < y && y < maxY;
        }
    }


    Slide[] slides;
    Point[] points;
    int[] sliding;
    int V;
    void solve() {
        int cnt = 0;
        while (true){
            int n = ni();
            if (n == 0) break;
            ++cnt;
            V = 2 * n;
            init(V);

            slides = new Slide[n];
            points = new Point[n];

            for (int i = 0; i < n; ++i) {
                int minX = ni();
                int maxX = ni();
                int minY = ni();
                int maxY = ni();
                slides[i] = new Slide(minX, maxX, minY, maxY);
            }

            for (int i = 0; i < n; ++i) {
                int x = ni();
                int y = ni();
                points[i] = new Point(x, y);
            }

            sliding = new int[n];
            Arrays.fill(sliding, -1);
            for (int i = 0; i < n; ++i){

                for (int j = 0; j < n; ++j){
                    if (slides[i].contain(points[j])){
                        clear();
                        for (int k = 0; k < n; ++k){
                            for (int l = 0; l < n; ++l){
                                if (l == j && k == i) continue;
                                if (slides[k].contain(points[l])){
                                    addEdge(k, l + n);
                                }
                            }
                        }

                        if (bipartiteMatching() == n - 1){
                            sliding[i] = j;
                        }
                    }
                }
            }
            out.println("Heap " + cnt);
            StringBuilder sb = new StringBuilder();
            boolean hasOne = false;
            for (int i = 0; i < n; ++i){
                if (sliding[i] >= 0){
                    char c = (char) ('A' + i);
                    sb.append("(" + c + "," + (sliding[i] + 1) + ")" + " ");
                    hasOne = true;
                }
            }
            if (hasOne)
                out.println(sb.toString().substring(0, sb.length() - 1));
            else
                out.println("none");
            out.println();
        }
    }

    //二分图匹配
    List<Integer>[] g;
    int[] matching;
    public void init(int V){
        g = new ArrayList[V];
        for (int i = 0; i < V; ++i) g[i] = new ArrayList<Integer>();
        matching = new int[V];
    }

    public void clear(){
        for (int i = 0; i < V; ++i){
            g[i].clear();
        }
    }


    public void addEdge(int from, int to){
        g[from].add(to);
        g[to].add(from);
    }



    public boolean dfs(int v, boolean[] visited){
        visited[v] = true;
        for (int u : g[v]){
            int w = matching[u];
            if (w == -1 || !visited[w] && dfs(w, visited)){
                matching[u] = v;
                matching[v] = u;
                return true;
            }
        }
        return false;
    }

    public int bipartiteMatching(){
        int cnt = 0;
        Arrays.fill(matching, -1);
        for (int i = 0; i < V; ++i){
            if (matching[i] < 0){
                if (dfs(i, new boolean[V])){
                    cnt ++;
                }
            }
        }
        return cnt;
    }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 挑战程序竞赛系列(21):3.2反转

    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.n...

    用户1147447
  • 挑战程序竞赛系列(28):3.5最小费用流

    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.n...

    用户1147447
  • K-th Smallest Prime Fraction

    思路1: 一种聪明的做法,如果A = [1, 7, 23, 29, 47],那么有:

    用户1147447
  • 挑战程序竞赛系列(32):4.5 A*与IDA*

    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.n...

    用户1147447
  • Day2上午解题报告

    预计分数:100+0+60=160 实际分数:100+0+60=160 mmpT1数据错了。。。 T1遭遇 题目描述 你是能看到第一题的 friends呢。 —...

    attack
  • 口算训练 HDU - 6287

    小Q非常喜欢数学,但是他的口算能力非常弱。因此他找到了小T,给了小T一个长度为n的正整数序列a1,a2,…,an,要求小T抛出m个问题以训练他的口算能力。

    用户7727433
  • 基数排序简介及其并行化

      基数排序号称线性时间排序算法中性能最好,速度最快的排序算法。本文将简要概括其算法思想,串行代码及其并行化。

    Dabelv
  • 浙大版《C语言程序设计(第3版)》题目集 习题6-2 使用函数求特殊a串数列和

    给定两个均不超过9的正整数a和n,要求编写函数求a+aa+aaa++⋯+aa⋯a(n个a)之和。

    C you again 的博客
  • 浙大版《C语言程序设计(第3版)》题目集 习题5-4 使用函数求素数和

    其中函数prime当用户传入参数p为素数时返回1,否则返回0;函数PrimeSum返回区间[m, n]内所有素数的和。题目保证用户传入的参数m≤n。

    C you again 的博客
  • 洛谷P1043 数字游戏

    题目描述 丁丁最近沉迷于一个数字游戏之中。这个游戏看似简单,但丁丁在研究了许多天之后却发觉原来在简单的规则下想要赢得这个游戏并不那么容易。游戏是这样的,在你面前...

    attack

扫码关注云+社区

领取腾讯云代金券