POJ2749 題解

題目大意：有若干牛圈和兩個連接起來的的中轉點S1，S2，每個牛圈需要選擇其中一個中轉點與之連接，從而使任意兩個牛圈能夠連通，有若干對牛圈里的牛互相hate或是互相like，若兩個牛圈里的牛互相hate，就不能連接到同一個中轉點上，而如果互相like，就必須連接到同一個中轉點上，連接方案還要使兩個牛圈之間的距離的最大值盡可能小，并求出這個值，

思路：2-SAT+二分，對每個牛圈x，令x為與S1連接，?x為與S2連接，接下來，對于每對互相hate的奶牛所在的牛圈a，b不能連接到同一個中轉點上，所以連邊（a，?b），（?b，a），（b，?a），（?a，b），對于每對互相like的奶牛所在的牛圈a，b必須連接到同一個中轉點上，所以連邊（a，b），（b，a），（?a，?b），（?b，?a），之后要讓所有連接起來的牛圈之間的距離的最大值盡量小，可以用二分，對每個距離，列舉所有相互連接的牛圈，牛圈（a，b）之間的連接方式又可以分為4種情況：

1）都連接在S1上

2）都連接在S2上

3）a連接在S1上并且b連接在S2上

4）a連接在S2上并且b連接在S1上

如果哪種連接方式使a,b的距離大于當前距離，就加邊來限制這種連接，對于情況1），就連邊（a，?b）和（b，?a）情況2）類似地去連邊（?a，b）和（?b，a），對于情況3）就連邊（a，b）和（?b，?a）情況4）類似地去連邊（b，a）和（?a，?b）

最后如果二分沒能找到結果就說明無法連接，

代碼如下：

//POJ.2749
//Author: Prgl
#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)

typedef pair<int, int>P;
typedef vector<int>vec;

#define INF 0x3f3f3f3f
const double EPS = 1e-18;
const int MOD = 1e9 + 7;
const int maxv = 1001;
const int maxn = 501;

int V;
vec G[maxv], rG[maxv];
stack<int>s;
bool used[maxv];
int cmp[maxv];

int N, A, B;
int sx1, sy1, sx2, sy2, D;
int X[maxn], Y[maxn];
P a[maxn], b[maxn];
int d1[maxn], d2[maxn], d[maxn];
bool one[maxn];

inline void add_edge(int from, int to)
{
	G[from].push_back(to);
	rG[to].push_back(from);
}

void add_edge_hate(int from, int to)
{
	add_edge(from, to + N);
	add_edge(to, from + N);
	add_edge(from + N, to);
	add_edge(to + N, from);
}

void add_edge_like(int from, int to)
{
	add_edge(from + N, to + N);
	add_edge(to + N, from + N);
	add_edge(from, to);
	add_edge(to, from);
}

inline int dis(int x1, int y1, int x2, int y2)
{
	return abs(x1 - x2) + abs(y1 - y2);
}

void dfs(int v)
{
	used[v] = true;
	for (int i = 0; i < G[v].size(); i++)
	{
		if (!used[G[v][i]])
			dfs(G[v][i]);
	}
	s.push(v);
}

void rdfs(int v, int k)
{
	cmp[v] = k;
	used[v] = true;
	for (int i = 0; i < rG[v].size(); i++)
	{
		if (!used[rG[v][i]])
			rdfs(rG[v][i], k);
	}
}

int scc()
{
	memset(used, 0, sizeof(used));
	for (int v = 0; v < V; v++)
	{
		if (!used[v])
			dfs(v);
	}
	memset(used, 0, sizeof(used));
	int k = 0;
	while (!s.empty())
	{
		int v = s.top();
		s.pop();
		if (!used[v])
			rdfs(v, k++);

	}

	return k;
}

bool C(int md)
{
	for (int i = 0; i < V; i++)
	{
		G[i].clear();
		rG[i].clear();
	}
	for (int i = 0; i < A; i++)
	{
		int u = a[i].first - 1, v = a[i].second - 1;
		add_edge_hate(u, v);
	}
	for (int i = 0; i < B; i++)
	{
		int u = b[i].first - 1, v = b[i].second - 1;
		add_edge_like(u, v);
	}
	for (int i = 0; i < N - 1; i++)
	{
		for (int j = i + 1; j < N; j++)
		{
			if (d1[i] + d1[j] > md)
			{
				add_edge(i, j + N);
				add_edge(j, i + N);
			}
			if (d2[i] + d2[j] > md)
			{
				add_edge(j + N, i);
				add_edge(i + N, j);
			}
			if (D + d1[i] + d2[j] > md)
			{
				add_edge(i, j);
				add_edge(j + N, i + N);
			}
			if (D + d2[i] + d1[j] > md)
			{
				add_edge(j, i);
				add_edge(i + N, j + N);
			}
		}
	}
	scc();
	for (int i = 0; i < N; i++)
	{
		if (cmp[i] == cmp[i + N])
			return false;
	}

	return true;
}

void solve()
{
	V = N * 2;
	D = dis(sx1, sy1, sx2, sy2);
	for (int i = 0; i < N; i++)
	{
		d1[i] = dis(X[i], Y[i], sx1, sy1);
		d2[i] = dis(X[i], Y[i], sx2, sy2);
	}
	int lo = -1, hi = 12000001;
	while (hi - lo > 1)
	{

		int mi = (hi + lo) / 2;
		if (C(mi))
			hi = mi;
		else
			lo = mi;
	}
	if (lo == 12000000)
		cout << -1 << endl;
	else
		cout << hi << endl;
}

int main()
{
	IOS;
	cin >> N >> A >> B;
	cin >> sx1 >> sy1 >> sx2 >> sy2;
	for (int i = 0; i < N; i++)
		cin >> X[i] >> Y[i];
	for (int i = 0; i < A; i++)
	{
		int u, v;
		cin >> u >> v;
		a[i] = P(u, v);
	}
	for (int i = 0; i < B; i++)
	{
		int u, v;
		cin >> u >> v;
		b[i] = P(u, v);
	}
	solve();

	return 0;
}