POJ_2749
一开始没有想到去二分距离，看了别人的报告之后恍然大悟。
这是一个2-SAT的问题，首先我们要去找到核心变量，可以看出每个牛的有着要么和S1相连，要么和S2相连的逻辑关系，因此可以把奶牛看做核心变量，并用2*i表示第i个奶牛和S1相连，用2*i+1表示和S2相连。
首先，我们要喜爱和憎恨的关系转化成边。如果i和j相互憎恨，那么如果i连S1，那么j必然连S2，如果i连S2，那么j必然连S1，反过来也是一样的。于是我们需要连4条边，分别是i->~j、~i->j、j->~i、~j->i。对于喜爱的关系，同理也需要连4条边，分别是i->j、~i->~j、j->i、~j->~i。
其次，我们需要找到两两之间最大距离的最小值。我们可以采用二分枚举的方式求解，设二分的距离值为mid，S1与S2的距离值为D，奶牛与S1的距离为dis1[]，奶牛与S2的距离为dis2[]，我们可以得到下列限制条件，并将其转化成边：
①如果dis1[i]+dis1[j]>mid，即i和j不能同时和S1相连，于是我们可以得到2条边，i->~j、j->~i。
②如果dis2[i]+dis2[j]>mid，即i和j不能同时和S2相连，于是我们又可以得到2两边，~i->j、~j->i。
③如果dis1[i]+D+dis2[j]>mid，即不能出现这种情况：i与S1相连，同时j与S2相连，于是有i->j、~j->~i。
④如果dis2[i]+D+dis1[j]>mid，即不能出现这种情况：i与S2相连，同时j与S1相连，于是有~i->~j、j->i。
如果没有一种可行的方案，需要输出-1。
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define MAXN 1500
#define MAXM 3000000
#define INF 12000000
int A, B, N, D, sx1, sy1, sx2, sy2, x[MAXN], y[MAXN];
int first[MAXN], next[MAXM], v[MAXM], e, dis[2][MAXN];
int dfn[MAXN], low[MAXN], cnt, s[MAXN], top, ins[MAXN];
int color[MAXN], col;
int hate[2][MAXN], love[2][MAXN];
void init()
{
int i;
scanf("%d%d%d%d", &sx1, &sy1, &sx2, &sy2);
D = abs(sx1 - sx2) + abs(sy1 - sy2);
for(i = 0; i < N; i ++)
{
scanf("%d%d", &x[i], &y[i]);
dis[0][i] = abs(x[i] - sx1) + abs(y[i] - sy1);
dis[1][i] = abs(x[i] - sx2) + abs(y[i] - sy2);
}
for(i = 0; i < A; i ++)
{
scanf("%d%d", &hate[0][i], &hate[1][i]);
hate[0][i] --;
hate[1][i] --;
}
for(i = 0; i < B; i ++)
{
scanf("%d%d", &love[0][i], &love[1][i]);
love[0][i] --;
love[1][i] --;
}
}
void add_edge(int i, int j)
{
v[e] = j;
next[e] = first[i];
first[i] = e;
e ++;
}
void build(int mid)
{
int i, j, k;
e = 0;
memset(first, -1, sizeof(first));
for(i = 0; i < A; i++)
{
add_edge(2 * hate[0][i], 2 * hate[1][i] + 1);
add_edge(2 * hate[0][i] + 1, 2 * hate[1][i]);
add_edge(2 * hate[1][i], 2 * hate[0][i] + 1);
add_edge(2 * hate[1][i] + 1, 2 * hate[0][i]);
}
for(i = 0; i < B; i++)
{
add_edge(2 * love[0][i], 2 * love[1][i]);
add_edge(2 * love[0][i] + 1, 2 * love[1][i] + 1);
add_edge(2 * love[1][i], 2 * love[0][i]);
add_edge(2 * love[1][i] + 1, 2 * love[0][i] + 1);
}
for(i = 0; i < N; i ++)
for(j = i + 1; j < N; j ++)
{
if(dis[0][i] + dis[0][j] > mid)
{
add_edge(2 * i, 2 * j + 1);
add_edge(2 * j, 2 * i + 1);
}
if(dis[1][i] + dis[1][j] > mid)
{
add_edge(2 * i + 1, 2 * j);
add_edge(2 * j + 1, 2 * i);
}
if(dis[0][i] + D + dis[1][j] > mid)
{
add_edge(2 * i, 2 * j);
add_edge(2 * j + 1, 2 * i + 1);
}
if(dis[1][i] + D + dis[0][j] > mid)
{
add_edge(2 * i + 1, 2 * j + 1);
add_edge(2 * j, 2 * i);
}
}
}
void tarjan(int u)
{
int i;
dfn[u] = low[u] = ++ cnt;
for(i = first[u]; i != -1; i = next[i])
{
if(!dfn[v[i]])
{
s[top ++] = v[i];
ins[v[i]] = 1;
tarjan(v[i]);
if(low[v[i]] < low[u])
low[u] = low[v[i]];
}
else if(ins[v[i]] && dfn[v[i]] < low[u])
low[u] = dfn[v[i]];
}
if(low[u] == dfn[u])
{
for(s[top] = -1; s[top] != u;)
{
top --;
ins[s[top]] = 0;
color[s[top]] = col;
}
col ++;
}
}
int com(int mid)
{
int i, j;
build(mid);
cnt = top = col = 0;
memset(dfn, 0, sizeof(dfn));
memset(ins, 0, sizeof(ins));
for(i = 0 ; i < 2 * N; i ++)
if(!dfn[i])
{
s[top ++] = i;
ins[i] = 1;
tarjan(i);
}
for(i = 0; i < 2 * N; i ++)
if(color[i] == color[i ^ 1])
return 0;
return 1;
}
int main()
{
int i, j, k, mid, max, min;
while(scanf("%d%d%d", &N, &A, &B) == 3)
{
init();
max = INF + 1;
min = -1;
for(;;)
{
mid = (max + min + 1) / 2;
if(mid == max)
break;
if(com(mid))
max = mid;
else
min = mid;
}
printf("%d\n", max > INF ? -1 : max);
}
return 0;
}