# UVALive3211- Now or later(二分+2-SAT)

2022年11月23日
0 收藏 638 点赞 4,246 浏览 1378 个字

，如果布尔变量xi表示第i架飞机是否早着陆。唯一限制就是“时间差小于P的两个着陆时间不能同一时候满足。每一组不能同一时候满足的着陆时间相应一个子句，则整个约束条件相应于2-SAT问题的实例。

`#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>using namespace std;const int MAXN = 2005;struct TwoSAT{    int n;    vector<int> g[MAXN * 2];    bool mark[MAXN * 2];    int s[MAXN * 2], c;    bool dfs(int x) {        if (mark[x^1]) return false;        if (mark[x]) return true;        mark[x] = true;        s[c++] = x;        for (int i = 0; i < g[x].size(); i++)            if (!dfs(g[x][i])) return false;        return true;    }    void init(int n) {        this->n = n;        for (int i = 0; i < n * 2; i++)            g[i].clear();        memset(mark, 0, sizeof(mark));    }    void add_clause(int x, int xval, int y, int yval) {        x = x * 2 + xval;        y = y * 2 + yval;        g[x^1].push_back(y);        g[y^1].push_back(x);    }    bool solve() {        for (int i = 0; i < n * 2; i += 2)            if (!mark[i] && !mark[i + 1]) {                c = 0;                if (!dfs(i)) {                    while (c > 0) mark[s[--c]] = false;                    if (!dfs(i + 1)) return false;                }            }        return true;    }};TwoSAT solver;int n, T[MAXN][2];bool test(int diff) {    solver.init(n);    for (int i = 0; i < n; i++)        for (int a = 0; a < 2; a++)            for (int j = i + 1; j < n; j++)                for (int b = 0; b < 2; b++)                    if (abs(T[i][a] - T[j][b]) < diff)                        solver.add_clause(i, a^1, j, b^1);    return solver.solve();}int main() {    while (scanf("%d", &n) != EOF) {        memset(T, 0, sizeof(T));        int L = 0, R = 0;        for (int i = 0; i < n; i++)            for (int a = 0; a < 2; a++) {                scanf("%d", &T[i][a]);                R = max(R, T[i][a]);            }        while (L < R) {            int mid = L + (R - L + 1) / 2;            if (test(mid))                L = mid;            else                R = mid - 1;        }        printf("%d\n", L);    }    return 0;}`

python开发_常用的python模块及安装方法

Educational Codeforces Round 11 C. Hard Process 二分
C. Hard Process题目连接：http://www.codeforces.com/contest/660/problem/CDes…

zengkefu@server1:/usr/src\$ uname -aLinux server1 4.10.0-19-generic #21…

Android调用系统相机、自定义相机、处理大图片
Android调用系统相机和自定义相机实例本博文主要是介绍了android上使用相机进行拍照并显示的两种方式，并且由于涉及到要把拍到的照片显…

Struts的使用