題目鏈接

? ?本題是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 \stackrel{?}{v}$和$v\to \stackrel{?}{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;
}