UVa1466/LA4849 String Phone

题目链接

   本题是2010年icpc亚洲区域赛大田赛区的G题

题意

   平面网格上有n（n≤3000）个单元格，各代表一个重要的建筑物。为了保证建筑物的安全，警察署给每个建筑物派了一名警察，并配发了一些有绳电话以供联络。有绳电话是指长度固定的电话，且电话两端的距离必须保持不变。在本题中，坐标(x1,y1)和(x2,y2)之间的距离为|x1-x2|+|y1-y2|。以无向加权图的形式给出哪些警察之间会使用有绳电话，以及每根绳子的长度，如下图所示，这个图保证是连通的。

   现在已经确定每名警察所巡逻的建筑物，请判断是否存在一种方案：每个建筑物选定一个顶点安置电话，使得所有有绳电话都能正常使用。

分析

   先说一个坑点：题目说图保证是连通的，实际上可能不连通，要对各个连通分量单独处理。
   考虑满足距离要求的顶点其实可以分成两类（0：左下/右上、1：左上/右下）并且只能选择一类，每类也只能选则一个，假定有绳电话一端的建筑物选定了0/1类顶点，则另外一端建筑物选定的顶点类别可以通过二染色确定：此有绳电话权值的奇偶性已知（因为长度已知），另外一端建筑物只有选特定类别的顶点才能维持两端点距离的奇偶性与权值要求的相符，这里暂时不需要准确到距离与权值相同，后面做2-SAT来处理这一点即可。
   有绳电话一端的建筑物选定了顶点类别后，其所在连通分量的二染色方案如果不存在，那么这种选择不可行；如果二染色方案存在，根据距离需要权值相同的限制建边，用2-SAT解决：枚举有绳电话两端具体选择的点u，v，此时实际距离如果和权值不相同，则连边$u\to \tilde{v}$和$v\to \tilde{u}$

AC 代码

#include <iostream>
#include <cstring>
using namespace std;#define N 3010
int dx[][2] = {{0, 1}, {0, 1}}, dy[][2] = {{0, 1}, {1, 0}}, d[N][N], g0[N][N], g[N<<1][N<<1], c0[N], c[N<<1], f[N], x[N], y[N], color[N], s[N<<1], sn[N<<1], low[N<<1], pre[N<<1], clk, cc, p, m, n;int find(int x) {return x == f[x] ? x : f[x] = find(f[x]);
}bool bipartite(int u) {for (int i=0; i<c0[u]; ++i) {int v = g0[u][i], b = ((abs(x[u]-x[v]) + abs(y[u]-y[v])) ^ d[u][v] ^ color[u]) & 1;if (color[v] < 0) {color[v] = b;if (!bipartite(v)) return false;} else if (color[v] != b) return false;}return true;
}void add_clause(int u, int v) {g[u][c[u]++] = v^1; g[v][c[v]++] = u^1;
}bool dfs(int u) {low[u] = pre[u] = ++clk; s[p++] = u;for (int i=0, v; i<c[u]; ++i) if (!pre[v = g[u][i]]) {if (!dfs(v)) return false;low[u] = min(low[u], low[v]);} else if (!sn[v]) low[u] = min(low[u], pre[v]);if (low[u] == pre[u]) {++cc;while (true) {if (cc == sn[s[--p]^1]) return false;sn[s[p]] = cc;if (s[p] == u) break;}}return true;
}bool check(int r, int b) {memset(color, -1, sizeof(color)); color[r] = b;if (!bipartite(r)) return false;memset(c, p = 0, sizeof(c)); memset(pre, clk = 0, sizeof(pre)); memset(sn, cc = 0, sizeof(sn));for (r=1; r<=n; ++r) if (color[r] >= 0) for (int i=0; i<c0[r]; ++i) for (int j=0, a=g0[r][i]; j<2; ++j) {int xu = x[r] + dx[color[r]][j], yu = y[r] + dy[color[r]][j], u = r<<1 | j;for (int k=0; k<2; ++k) {int xv = x[a] + dx[color[a]][k], yv = y[a] + dy[color[a]][k], v = a<<1 | k;if (abs(xu-xv)+abs(yu-yv) != d[r][a]) add_clause(u, v);}}for (int u=2, m=(n+1)<<1; u<m; ++u) if (!pre[u] && !dfs(u)) return false;return true;
}void solve() {cin >> n;for (int i=1; i<=n; ++i) cin >> x[i] >> y[i], c0[i] = 0, f[i] = i;cin >> m;while (m--) {int u, v; cin >> u >> v >> d[u][v];d[v][u] = d[u][v]; g0[u][c0[u]++] = v; g0[v][c0[v]++] = u; f[find(u)] = find(v);}bool ok  = true;for (int i=1; i<=n; ++i) if (find(i) == i && !check(i, 0) && !check(i, 1)) {ok = false; break;}cout << (ok ? "possible" : "impossible") << endl;
}int main() {ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);int t; cin >> t;while (t--) solve();return 0;
}