每个牛棚跟一个中转站相连，求最小的任意两牛棚间的距离中的最大值
又是2—SAT+二分验证求最小的最大值，
2—SAT：如果a与b矛盾，建边a—>b‘；
枚举任意两牛棚之间的距离，如果大于最大距离，就要相反的方式连接，
刚开始没有考虑两个中转站的距离，结果一直不对，还以为算法有bug，郁闷了半天。
如果两牛棚连接在两个不同的中转站，两点间的距离要加上中转站的距离
#include<stdio.h>
#include<stack>
#include<string.h>
#define N 2000
#define M 1000
using namespace std;
struct edage
{
int ed;
int next;
}E[M*M];
struct op
{
int x,y;
}P[N],P0,P1;
int n,low[N],dfs[N],ins[N],map[N*2],idx,ans,first[N],rfirst[N],belong[N],num,rnum,len;
stack<int>Q;
void addeage(int x,int y)
{
E[num].ed=y;
E[num].next=first[x];
first[x]=num++;
}
int dis(op a,op b)
{
return abs(a.x-b.x)+abs(a.y-b.y);
}
void Tarjan(int x)
{
int p,v;
low[x]=dfs[x]=idx++;
ins[x]=1;
Q.push(x);
for(p=first[x];p!=-1;p=E[p].next)
{
v=E[p].ed;
if(dfs[v]==-1)
{
Tarjan(v);
low[x]=low[x]>low[v]?low[v]:low[x];
}
else if(ins[v]==1)
{
low[x]=low[x]>dfs[v]?dfs[v]:low[x];
}
}
if(dfs[x]==low[x])
{
do
{
v=Q.top();
Q.pop();
ins[v]=0;
belong[v]=ans;
}while(v!=x);
ans++;
}
}
int sum=0;
int judge(int d,int min,int max)
{
int i,j;
memcpy(first,rfirst,sizeof(first));
num=rnum;
for(i=1;i<=n;i++)//枚举两点之间的距离
for(j=i+1;j<=n;j++)
{
if(map[i]+map[j]>d)//连接相同同中转站不符合
{
addeage(i,j+n);
addeage(j,i+n);
}
if(map[i]+map[j+n]+len>d)//连接不同的中转站不符合
{
addeage(i,j);
addeage(j+n,i+n);
}
if(map[i+n]+map[j]+len>d)//连接不同的中转站不符合
{
addeage(i+n,j+n);
addeage(j,i);
}
if(map[i+n]+map[j+n]>d)//连接相同同中转站不符合
{
addeage(i+n,j);
addeage(j+n,i);
}
}
memset(low,0,sizeof(low));
memset(ins,0,sizeof(ins));
memset(dfs,-1,sizeof(dfs));
memset(belong,0,sizeof(belong));
idx=ans=1;
for(i=1;i<=n*2;i++)
{
if(dfs[i]==-1)
Tarjan(i);
}
for(i=1;i<=n;i++)
if(belong[i]==belong[i+n])
return 0;
return 1;
}
int main()
{
int i,m,k,min,max,mid,flag,x,y,mmax;
while(scanf("%d%d%d",&n,&m,&k)!=-1)
{
memset(first,-1,sizeof(first));
num=0;
scanf("%d%d%d%d",&P0.x,&P0.y,&P1.x,&P1.y);
for(i=1;i<=n;i++)
scanf("%d%d",&P[i].x,&P[i].y);
min=999999999;
max=-1;
for(i=1;i<=n;i++)
{
map[i]=dis(P[i],P0);
map[i+n]=dis(P[i],P1);
if(min>map[i])
min=map[i];
if(min>map[i+n])
min=map[i+n];
if(max<map[i])
max=map[i];
if(max<map[i+n])
max=map[i+n];
}
len=dis(P0,P1);
for(i=0;i<m;i++)
{
scanf("%d%d",&x,&y);
addeage(x,y+n);
addeage(y,x+n);
addeage(x+n,y);
addeage(y+n,x);
}
for(i=0;i<k;i++)
{
scanf("%d%d",&x,&y);
addeage(x,y);
addeage(x+n,y+n);
addeage(y,x);
addeage(y+n,x+n);
}
memcpy(rfirst,first,sizeof(first));
rnum=num;
min=min*2,max=max*2+len;
mmax=-1;flag=0;
while(min<=max)
{
mid=(min+max)/2;
if(judge(mid,min,max))
{
max=mid-1;
mmax=mid;
}
else min=mid+1;
}
printf("%d\n",mmax);
}
return 0;
}