[POJ 2749] 二分枚举、2-SAT判定

【题目大意】 有两个中转站，和N个点。每个点要么连到1号中转站，要么连到2号中转站。给出一些限制信息，即哪两个点必须连到一个中转站上，哪两个点必须不能连到一个中转站上。若两个点在同一中转站上，则距离是两者到中转站的距离和，否则是两者到中转站的距离和加上中转站之间的距离。求一种方案，使得任意两点之间的最大距离最小。

【算法分析】先二分枚举答案，将每只牛拆成连左边和连右边两个点，然后按以下方式连边进行2-SAT判定。（i表示连左边，i’表示连右边）
1、HATE I J ————->[I,J’]         [I’,J]        [J,I’]        [J’,I]
2、LOVE I J————-> [I,J]          [I’,J’]       [J,I]         [J’,I’]
3、这个根据题目的距离来搞，情况比较多，直接贴代码部分。。。
（d1[i]表示与第一个中转站的距离，d2[i]表示与第二个中转站的距离，d12为两个中转站的距离）
for (int i=1;i<=n;i++)
for (int j=i+1;j<=n;j++){
// ll
if (d1[i]+d1[j]>limit){
add(i,j+n);
add(j,i+n);
}
// lr
if (d12+d1[i]+d2[j]>limit){
add(i,j);
add(j+n,i+n);
}
// rl         
if (d12+d2[i]+d1[j]>limit){
add(i+n,j+n);
add(j,i);
}
// rr         
if (d2[i]+d2[j]>limit){
add(i+n,j);
add(j+n,i);
}   
}

【其它】1A
6398552 edward2 2749 Accepted 7096K 516MS G++ 2987B 2010-02-01 23:16:41
【CODE】
#include #include #include #define N 1200
#define inf 100000000
struct edge {int y,next;}g[1000000];
int n,a,b,ls[N],hate[2][N],love[2][N],x[N],y[N],sx1,sx2,sy1,sy2;
int d1[N],d2[N],d[501][501],d12,f[N],dep[N],color[N],e;

void init(){
scanf("%d%d%d",&n,&a,&b);
scanf("%d%d%d%d",&sx1,&sy1,&sx2,&sy2);
for (int i=1;i<=n;i++) scanf("%d%d",&x[i],&y[i]);
for (int i=1;i<=a;i++) scanf("%d%d",&hate[0][i],&hate[1][i]);
for (int i=1;i<=b;i++) scanf("%d%d",&love[0][i],&love[1][i]);
for (int i=1;i<=n;i++){
d1[i]=abs(x[i]-sx1)+abs(y[i]-sy1);
d2[i]=abs(x[i]-sx2)+abs(y[i]-sy2);
}
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
d[i][j]=abs(x[i]-x[j])+abs(y[i]-y[j]);
d12=abs(sx1-sx2)+abs(sy1-sy2);
}

int gf(int k){
if (f[k]==k) return k;
f[k]=gf(f[k]);
return f[k];
}

void dfs(int k){
for (int t=ls[k];t;t=g[t].next)
if (!dep[g[t].y]){
dep[g[t].y]=dep[k]+1;
dfs(g[t].y);
if (dep[gf(g[t].y)] f[k]=f[g[t].y];
}
else if (!color[gf(g[t].y)] && dep[gf(g[t].y)] f[k]=f[g[t].y];
color[k]=1;
}

void tarjan(){
for (int i=1;i<=2*n;i++){
f[i]=i;
dep[i]=0;
color[i]=0;
}
for (int i=1;i<=2*n;i++)
if (!dep[i]){
dep[i]=1;
dfs(i);
}
for (int i=1;i<=2*n;i++) gf(i);
}

void add(int x,int y){
e++;
g[e].y=y; g[e].next=ls[x]; ls[x]=e;
}

bool flag(int limit){
e=0; for (int i=1;i<=2*n;i++) ls[i]=0;
for (int i=1;i<=a;i++){
add(hate[0][i],hate[1][i]+n);
add(hate[1][i],hate[0][i]+n);
add(hate[0][i]+n,hate[1][i]);
add(hate[1][i]+n,hate[0][i]);
}
for (int i=1;i<=b;i++){
add(love[0][i],love[1][i]);
add(love[1][i],love[0][i]);
add(love[0][i]+n,love[1][i]+n);
add(love[1][i]+n,love[0][i]+n);
}
for (int i=1;i<=n;i++)
for (int j=i+1;j<=n;j++){
// ll
if (d1[i]+d1[j]>limit){
add(i,j+n);
add(j,i+n);
}
// lr
if (d12+d1[i]+d2[j]>limit){
add(i,j);
add(j+n,i+n);
}
// rl
if (d12+d2[i]+d1[j]>limit){
add(i+n,j+n);
add(j,i);
}
// rr
if (d2[i]+d2[j]>limit){
add(i+n,j);
add(j+n,i);
}
}
tarjan();
for (int i=1;i<=n;i++)
if (f[i]==f[i+n]) return false;
return true;
}

int main(){
init ();
if (!flag(inf)) printf("-1n");
else{
int l=0,r=inf,mid;
while (l mid=(l+r)/2;
if (flag(mid)) r=mid;
else l=mid+1;
}
printf("%dn",l);
}
return 0;
}