挑战程序竞赛系列(77):4.3 2-SAT(1)

挑战程序竞赛系列(77):4.3 2-SAT(1)

传送门:POJ 3683: Priest John’s Busiest Day

题意:

有n个婚礼,每个婚礼有起始时间si,结束时间ti,还有一个主持时间ti,ti必须安排在婚礼的开始或者结束,主持由祭祀来做,但是只有一个祭祀,所以各个婚礼的主持时间不能重复,问你有没有可能正常的安排主持时间,不能输出no,能的话要输出具体的答案:即每个婚礼的主持时间段是什么样

2-SAT,第一接触,参考了博文: http://blog.csdn.net/moguxiaozhe/article/details/49047085

其中的参考资料也可以读一读,不难理解,《挑战》上的解释有点学术化,简单来说,对应于每一组,都有两种状态,每两组之间的状态可能出现矛盾,于是排除互不相容的状态,最终看对应的每一组,能否选出一个状态序列,使得每组都相容。

解决思路:传统暴力,每组只有两种状态,对应于选状态1和选状态2,总共遍历2n2^n次,找寻出相容的状态序列。

实际情况,如果A1 和 B1 不相容,则A1 一定选择 B2,对应的B1一定选择A2,有了这样的关系,可以构建一个关系图,而我们知道,在一个环内的结点,两两都能任意抵达,而对应的它们各自的互异状态同样能构成环。

如上1和3之所以能构成环是因为矛盾关系1和4, 2和3共同构成的,而对应的2和4也构成了环,上下对称,所以我们可以利用SCC的强连通分量算法把它们看作一个缩点。

对于非法状态,很容易理解,只要其中任何一组的两个状态存在一个强连通分量中即出现了矛盾。

合法的状态序列比较难以理解:个人认为是在求解(1,3)的连通分量并标记时,它连带的顶点(8)一定在标记前者时就近被访问标记了,而7只能是在标记(2,4)前后发生,而我们知道(1,3,8)和(2,4,8)互不相连,所以它们之间的序一定是同大或者同小。

所以有了:

    for (int i = 0; i < N; ++i) {
        if (vs[2 * i].comp == vs[2 * i + 1].comp) {
            out.println("NO");
            return;
        }
    }

    out.println("YES");
    for (int i = 0; i < N; ++i) {
        if (vs[2 * i].comp > vs[2 * i + 1].comp) {
            printf(S[i], S[i] + D[i]);
        }
        else {
            printf(T[i] - D[i], T[i]);
        }
    }

采用《挑战》的scc代码MLE了,更新了一波最新的SCC算法。

代码如下:

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.List;
import java.util.StringTokenizer;

class SCC {
    public static int n;
    public static V[] us;

    public static int scc(V[] vs) {
        n = vs.length;
        us = new V[n];
        for (V v : vs) if (!v.visit) dfs(v);
        for (V v : vs) v.visit = false;
        for (V u : us) if (!u.visit) dfsRev(u, n++);
        return n;
    }

    public static void dfs(V v) {
        v.visit = true;
        for (V u : v.fs) if (!u.visit) dfs(u);
        us[--n] = v;
    }

    public static void dfsRev(V v, int k) {
        v.visit = true;
        for (V u : v.rs) if (!u.visit) dfsRev(u, k);
        v.comp = k;
    }


    public static class V {
        public boolean visit;
        public int comp;
        public List<V> fs = new ArrayList<V>();
        public List<V> rs = new ArrayList<V>();

        public void add(V u) {
            fs.add(u);
            u.rs.add(this);
        }
    }
}

public class Main{

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

    public static void main(String[] args) throws IOException {
        new Main().run();
    }
    static final int MAX_N = 1000 + 16;
    int[] S = new int[MAX_N], T = new int[MAX_N], D = new int[MAX_N];
    int N;


    void read() {
        N = ni();
        for (int i = 0; i < N; ++i) {
            String ss = ns();
            String tt = ns();
            D[i] = ni();
            S[i] = Integer.parseInt(ss.substring(0, 2)) * 60 + Integer.parseInt(ss.substring(3));
            T[i] = Integer.parseInt(tt.substring(0, 2)) * 60 + Integer.parseInt(tt.substring(3));
        }
        solve();
    }

    boolean cross(int a, int b, int l, int r) {
        return a < r && l < b;
    }

    void solve() {
        SCC.V[] vs = new SCC.V[N * 2];
        for (int i = 0; i < vs.length; ++i) {
            vs[i] = new SCC.V();
        }
        for (int i = 0; i < N; ++i) {
            for (int j = i + 1; j < N; ++j) {
                if (cross(S[i], S[i] + D[i], S[j], S[j] + D[j])) {
                    vs[2 * i].add(vs[2 * j + 1]);
                    vs[2 * j].add(vs[2 * i + 1]);
                }
                if (cross(S[i], S[i] + D[i], T[j] - D[j], T[j])) {
                    vs[2 * i].add(vs[2 * j]);
                    vs[2 * j + 1].add(vs[2 * i + 1]);
                }
                if (cross(T[i] - D[i], T[i], S[j], S[j] + D[j])) {
                    vs[2 * i + 1].add(vs[2 * j + 1]);
                    vs[2 * j].add(vs[2 * i]);
                }
                if (cross(T[i] - D[i], T[i], T[j] - D[j], T[j])) {
                    vs[2 * i + 1].add(vs[2 * j]);
                    vs[2 * j + 1].add(vs[2 * i]);
                }
            }
        }

        SCC.scc(vs);
        for (int i = 0; i < N; ++i) {
            if (vs[2 * i].comp == vs[2 * i + 1].comp) {
                out.println("NO");
                return;
            }
        }

        out.println("YES");
        for (int i = 0; i < N; ++i) {
            if (vs[2 * i].comp > vs[2 * i + 1]. comp) {
                printf(S[i], S[i] + D[i]);
            }
            else {
                printf(T[i] - D[i], T[i]);
            }
        }
    }

    void printf(int s, int t) {
        out.printf("%02d:%02d %02d:%02d\n", s / 60, s % 60, t / 60, t % 60);
    }

    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);
        }
    }
}

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏拂晓风起

SWF运行时判断两个DisplayObject是否同个类型,属于flash professional库中的同一个元件

973
来自专栏机器学习入门

POJ 刷题系列:2739. Sum of Consecutive Prime Numbers

POJ 刷题系列:2739. Sum of Consecutive Prime Numbers 传送门:POJ 2739. Sum of Consecutive...

1857
来自专栏跟着阿笨一起玩NET

C# 使用 NPOI 库读写 Excel 文件

NPOI 是开源的 POI 项目的.NET版,可以用来读写Excel,Word,PPT文件。在处理Excel文件上,NPOI 可以同时兼容 xls 和 xlsx...

361
来自专栏用户画像

java 五子棋

662
来自专栏Hongten

java的jxl技术导入Excel

http://www.cnblogs.com/hongten/gallery/image/112177.html

692
来自专栏技术碎碎念

windows API 开发飞机订票系统 图形化界面 (三)

来吧,接下来是各个功能的函数的实现代码。 首先,程序运行时加载读入账户信息和航班信息。接下来就该读取文件了。 我把账户资料和航班信息储存在了.txt文件里 那么...

37914
来自专栏机器学习入门

挑战程序竞赛系列(85):3.6极限情况(2)

挑战程序竞赛系列(85):3.6极限情况(2) 传送门:POJ 1418: Viva Confetti 题意: 礼花:Confetti 是一些大小不一的彩色圆...

1845
来自专栏机器学习入门

POJ 刷题系列:2262. Goldbach's Conjecture

POJ 刷题系列:2262. Goldbach’s Conjecture 传送门:POJ 2262. Goldbach’s Conjecture 题意: 给定...

1506
来自专栏ml

数据挖掘之聚类算法Apriori总结

项目中有时候需要用到对数据进行关联分析,比如分析一个小商店中顾客购买习惯. 1 package com.data.algorithm; 2 3 i...

3487
来自专栏技术记录

im4java包处理图片

使用方法:首先要安装ImageMagick这个工具,安装好这个工具后,再下载im4java包放到项目lib目录里就行了。 package com.stu.uti...

2426

扫码关注云+社区