POJ2749 题解

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;elselo = mi;}if (lo == 12000000)cout << -1 << endl;elsecout << 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;
}