【题目链接】
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=3587
【题目大意】
有n架飞机要着陆, 每架飞机都可以选择“早着陆”或者“晚着陆”中的一种,不能在其他时间着陆。 给出每架飞机“早着陆”和“玩着陆”的时间, 问怎样安排着陆,才可以使得着任意两架飞机的陆时间间隔最小,输出最小值。
【思路】
水题,二分最小间隔时间,用2-SAT判断。
【代码】
#include<iostream>
#include<queue>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
const int MAXN = 2005;
const int VN = MAXN*2;
const int EN = MAXN*MAXN*4;
int n, m;
int t[MAXN][2];
struct Graph{
int size, head[VN];
struct{int v, next; }E[EN];
void init(){size=0; memset(head, -1, sizeof(head));}
void addEdge(int u, int v){
E[size].v = v;
E[size].next = head[u];
head[u] = size++;
}
}g;
class Two_Sat{
public:
bool check(){
scc();
for(int i=0; i<n; ++i)
if(belong[i] == belong[i+n])
return false;
return true;
}
private:
void tarjan(const int u){
int v;
low[u] = dfn[u] = ++idx;
instack[u] = true;
sta[top++] = u;
for(int e=g.head[u]; e!=-1; e=g.E[e].next){
v = g.E[e].v;
if(dfn[v] == -1){
tarjan(v);
low[u] = min(low[u], low[v]);
}else if(instack[v])
low[u] = min(low[u], dfn[v]);
}
if(dfn[u] == low[u]){
++bcnt;
do{
v = sta[--top];
instack[v] = false;
belong[v] = bcnt;
}while(u != v);
}
}
void scc(){
idx = top = bcnt = 0;
memset(instack, 0, sizeof(instack));
memset(dfn, -1, sizeof(dfn));
for(int i=0; i<2*n; ++i)
if(dfn[i] == -1)
tarjan(i);
}
private:
int idx, top, bcnt;
int sta[VN], low[VN], dfn[VN], belong[VN];
bool instack[VN];
}sat;
void buildGraph(int minT){
g.init();
for(int i=0; i<n; ++i){
for(int j=i+1; j<n; ++j){
int ta1=t[i][0], ta2=t[i][1];
int tb1=t[j][0], tb2=t[j][1];
if(abs(ta1-tb1) < minT){
g.addEdge(i, j+n);
g.addEdge(j, i+n);
}
if(abs(ta1-tb2) < minT){
g.addEdge(i, j);
g.addEdge(j+n, i+n);
}
if(abs(ta2-tb1) < minT){
g.addEdge(i+n, j+n);
g.addEdge(j, i);
}
if(abs(ta2-tb2) < minT){
g.addEdge(i+n, j);
g.addEdge(j+n, i);
}
}
}
}
int main(){
while(~scanf("%d", &n)){
for(int i=0; i<n; ++i)
scanf("%d%d", &t[i][0], &t[i][1]);
int l=0, r=1e7, mid, ans=-1;
while(l < r){
mid = (l+r)>>1;
buildGraph(mid);
if(sat.check()){
ans = mid;
l = mid+1;
}else
r = mid;
}
printf("%d\n", ans);
}
return 0;
}
分享到:
相关推荐
判断输入字符串是否为镜像或回文串。 来源于UVaOJ - 401. 水题。
开源项目-codingsince1985-UVa#uva-online-judge-solutions-in-golang.zip,两年来每天都在解决一个uva在线裁判问题,算起来…
uva705 Slash Maze 的代码,在UVaOJ上通过
PDF试题
Algorithm-UVA-Solutions-in-Python.zip,python 3中各种uva(acm)问题的解决方案。,算法是为计算机程序高效、彻底地完成任务而创建的一组详细的准则。
uva532 Dungeon Master的源代码,并且AC了
tpcw-nyu-uva-client 客户端
这是UVA133 TheDoleQueue救济金发放问题,经典的算法问题。初学算法的人要对这种算法非常熟悉并且能熟练运用。
CPP中的Postfix-Tree-Calculator:在C ++中实现后缀树计算器。 包括来自UVA CS部门的测试C ++文件