挑战程序竞赛系列（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);
}
}
}
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2017-09-25 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
