挑战程序竞赛系列(79):4.3 2-SAT(3)

挑战程序竞赛系列(79):4.3 2-SAT(3)

传送门:POJ 2723: Get Luffy Out

题意:

题目意思有点坑,实际上给出每一对钥匙,如(0,3),如果选择了钥匙0,那么后续的门只能用钥匙0开,而不能再选择3,意味着每对钥匙是可以开多扇门的。

思路: 二分+2-SAT,每一扇门有两把锁,一扇门能推出一对矛盾关系,如OJ上提供的数据:

3 6
0 3
1 2
4 5
0 1
0 2
4 1
4 2
3 5
2 2
0 0

第一扇门为:(0,1)
那么对应的钥匙串有(0,3)和(1,2)

开任意一把锁都能通过该层,如下:
钥匙串A 钥匙串B  门
0      1       通过
0      2       通过
3      1       通过
3      2       未通过

所以此处矛盾关系为3和2,即钥匙串1和钥匙串2不能同时选择3和2。
有了矛盾关系就可以根据2-SAT模型去解了。

二分:
显然,矛盾关系越多(每扇门一个约束条件),符合条件的钥匙串选择就越少,符合单调性,加快搜索。

代码如下:

import java.io.BufferedReader;
import java.io.File;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Map;
import java.util.StringTokenizer;

public class Main{

    String INPUT = "./data/judge/201709/P2723.txt";

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

    int[][] doors;
    int[] keys;
    int N, M;

    class SCC {
        int V;
        List<Integer>[] g;
        List<Integer>[] rg;
        List<Integer> po;
        boolean[] used;
        int[] cmp;

        SCC(int V){
            this.V = V;
            g  = new List[V];
            rg = new List[V];
            po = new ArrayList<Integer>();
            used = new boolean[V];
            cmp  = new int[V];
            for (int i = 0; i < V; ++i) g[i]  = new ArrayList<Integer>();
            for (int i = 0; i < V; ++i) rg[i] = new ArrayList<Integer>();
        }

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

        void dfs(int v) {
            used[v] = true;
            for (int u : g[v]) {
                if (!used[u]) dfs(u);
            }
            po.add(v);
        }

        void rdfs(int v, int k) {
            used[v] = true;
            cmp[v]  = k;
            for (int u : rg[v]) {
                if (!used[u]) rdfs(u, k);
            }
        }

        int kosarajuSCC() {
            for (int i = 0; i < V; ++i) {
                if (!used[i]) dfs(i);
            }
            Arrays.fill(used, false);
            int k = 0;
            for (int i = po.size() - 1; i >= 0; --i) {
                int v = po.get(i);
                if (!used[v]) rdfs(v, k++);
            }
            return k;
        }
    }

    void read() {
        while (true) {
            N = ni();
            M = ni();
            if (N + M == 0) break;

            keys = new int[2 * N];
            for (int i = 0; i < N; ++i) {
                int A = ni();
                int B = ni();
                keys[A] = B;
                keys[B] = A;
            }

            doors = new int[M][2];
            for (int i = 0; i < M; ++i) {
                doors[i] = new int[] {ni(), ni()};
            }

            solve();
        }
    }

    void solve() {
        int lf = 0, rt = M;
        while (lf < rt) {
            int mid = lf + (rt - lf + 1) / 2;
            if (!valid(mid)) {
                rt = mid - 1;
            }
            else {
                lf = mid;
            }
        }
        out.println(lf);
    }

    boolean valid(int m) {
        SCC scc = new SCC(2 * N);
        for (int i = 0; i < m; ++i) {
            scc.add(keys[doors[i][0]], doors[i][1]);
            scc.add(keys[doors[i][1]], doors[i][0]);
        }

        scc.kosarajuSCC();
        for (int i = 0; i < scc.V; ++i) {
            if (scc.cmp[i] == scc.cmp[keys[i]]) {
                return false;
            }
        }
        return true;
    }

    FastScanner in;
    PrintWriter out;

    void run() throws IOException {
        boolean oj;
        try {
            oj = ! System.getProperty("user.dir").equals("F:\\java_workspace\\leetcode");
        } catch (Exception e) {
            oj = System.getProperty("ONLINE_JUDGE") != null;
        }

        InputStream is = oj ? System.in : new FileInputStream(new File(INPUT));
        in = new FastScanner(is);
        out = new PrintWriter(System.out);
        long s = System.currentTimeMillis();
        read();
        out.flush();
        if (!oj){
            System.out.println("[" + (System.currentTimeMillis() - s) + "ms]");
        }
    }

    public boolean more(){
        return in.hasNext();
    }

    public int ni(){
        return in.nextInt();
    }

    public long nl(){
        return in.nextLong();
    }

    public double nd(){
        return in.nextDouble();
    }

    public String ns(){
        return in.nextString();
    }

    public char nc(){
        return in.nextChar();
    }

    class FastScanner {
        BufferedReader br;
        StringTokenizer st;
        boolean hasNext;

        public FastScanner(InputStream is) throws IOException {
            br = new BufferedReader(new InputStreamReader(is));
            hasNext = true;
        }

        public String nextToken() {
            while (st == null || !st.hasMoreTokens()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (Exception e) {
                    hasNext = false;
                    return "##";
                }
            }
            return st.nextToken();
        }

        String next = null;
        public boolean hasNext(){
            next = nextToken();
            return hasNext;
        }

        public int nextInt() {
            if (next == null){
                hasNext();
            }
            String more = next;
            next = null;
            return Integer.parseInt(more);
        }

        public long nextLong() {
            if (next == null){
                hasNext();
            }
            String more = next;
            next = null;
            return Long.parseLong(more);
        }

        public double nextDouble() {
            if (next == null){
                hasNext();
            }
            String more = next;
            next = null;
            return Double.parseDouble(more);
        }

        public String nextString(){
            if (next == null){
                hasNext();
            }
            String more = next;
            next = null;
            return more;
        }

        public char nextChar(){
            if (next == null){
                hasNext();
            }
            String more = next;
            next = null;
            return more.charAt(0);
        }
    }

    static class D{

        public static void pp(int[][] board, int row, int col) {
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < row; ++i) {
                for (int j = 0; j < col; ++j) {
                    sb.append(board[i][j] + (j + 1 == col ? "\n" : " "));
                }
            }
            System.out.println(sb.toString());
        }

        public static void pp(char[][] board, int row, int col) {
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < row; ++i) {
                for (int j = 0; j < col; ++j) {
                    sb.append(board[i][j] + (j + 1 == col ? "\n" : " "));
                }
            }
            System.out.println(sb.toString());
        }
    }

    static class ArrayUtils {

        public static void fill(int[][] f, int value) {
            for (int i = 0; i < f.length; ++i) {
                Arrays.fill(f[i], value);
            }
        }

        public static void fill(int[][][] f, int value) {
            for (int i = 0; i < f.length; ++i) {
                fill(f[i], value);
            }
        }

        public static void fill(int[][][][] f, int value) {
            for (int i = 0; i < f.length; ++i) {
                fill(f[i], value);
            }
        }
    }

    static class Num{
        public static <K> void inc(Map<K, Integer> mem, K k) {
            if (!mem.containsKey(k)) mem.put(k, 0);
            mem.put(k, mem.get(k) + 1);
        }
    }
}

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏专知

关关的刷题日记03—Leetcode 448. Find All Numbers Disappeared in an Array

题目 448. Find All Numbers Disappeared in an Array Given an array of integers wher...

2814
来自专栏章鱼的慢慢技术路

《算法图解》第六章笔记_广度优先搜索

1374
来自专栏专知

【关关的刷题日记58】Leetcode 112 Path Sum

关关的刷题日记58 – Leetcode 112 Path Sum 题目 ? 题目的意思是判断一棵二叉树跟到叶子节点的所有路径中是否有一条路径的和等于给定的和。...

3454
来自专栏mini188

学习笔记:Hashtable和HashMap

学了这么些天的基础知识发现自己还是个门外汗,难怪自己一直混的不怎么样。但这样的恶补不知道有没有用,是不是过段时间这些知识又忘了呢?这些知识平时的工作好像都是随拿...

1948
来自专栏数说工作室

【SAS Says】基础篇:描述性分析(上)

特别说明:本节【SAS Says】基础篇:描述性分析(上),用的是数说君学习《The little SAS book》时的中文笔记,我们认为这是打基础的最好选择...

3437
来自专栏数说工作室

5. call PRXCHANGE() | 移形换影

【SAS Says·扩展篇】移形换影 | 5. call PRXCHANGE() 0. 前集回顾 1. 新的问题 2. 初识 PRXCHANGE() 3. 问题...

3705
来自专栏Python小屋

Python花式编程案例集锦(8):判断吉祥数字

问题描述:在有些文化中,认为含有8的数字是吉祥数字,能给自己带来好运。要求编写一个函数测试给定的数字是否为吉祥数字。 参考代码: ? 代码运行没有输出,说明两种...

3296
来自专栏章鱼的慢慢技术路

《算法图解》第六章笔记

1555
来自专栏LinkedBear的个人空间

唠唠SE的面向对象-02——封装 原

1) 我们日常使用的电脑主机,把cpu、内存、主板等等都封装到机箱里面去。假如没有机箱的话的出现什么问题?

893
来自专栏康怀帅的专栏

Shell date 命令详解

以给定的格式显示当前时间。 %% 一个文字的 % %a 当前locale 的星期名缩写(例如: 日,代表星期日) %A 当前locale 的星...

3454

扫码关注云+社区