本文主要是介绍LA 3211 Now or later / 2-SAT，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
每架飞机只能在E L 这2个时间点降落 每2架并且降落的时间间隔必须大于等于p才算安全 目标使p尽量大
二分时间间隔 做2-SAT 有解说明可行
xi = true 表示选择E false 选择L
如果 abs(Ei - Ej) < p (p 是当前二分到的值) 那么 1.选择了Ei 必须选择Lj 2.选择了Ej 必须选择Li
建图 上模版
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;const int maxn = 2010;vector <int> G[maxn*2];
int n, T[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()
{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;
}
bool test(int diff)
{init();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)add_clause(i, a^1, j, b^1);}}}}return solve();
}int main()
{while(scanf("%d", &n) == 1){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 M = L + (R-L+1)/2;if(test(M))L = M;elseR = M-1;}printf("%d\n", L);}return 0;
}
这篇关于LA 3211 Now or later / 2-SAT的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
