傳送門：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=3726
一道看似博弈論的題，其實(shí)就是模板題而已。
分析：
平面上N個(gè)點(diǎn)，兩個(gè)人輪流取點(diǎn)，而且規(guī)定當(dāng)前取的點(diǎn)和上一個(gè)取的點(diǎn)的曼哈頓距離要小于L，所以，點(diǎn)可以看成兩兩成對(duì)消去。
這也就轉(zhuǎn)成了一般圖匹配，如果存在完美匹配，那么后手的人總可以取完，如果不存在，那么先手的人可以拿一個(gè)孤立點(diǎn)，這樣第二個(gè)人要么沒有匹配點(diǎn)，要么只能拆到一個(gè)匹配對(duì)，但這樣又造成了孤立點(diǎn)。
網(wǎng)上有個(gè)人拿二分圖匹配過(guò)了....看來(lái)數(shù)據(jù)很弱.....
代碼：
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <cmath>
#define MAXN 450
using namespace std;
int x[MAXN], y[MAXN];
struct Graph
{
bool mat[MAXN + 1][MAXN + 1];
int n;
bool inque[MAXN + 1];
int que[MAXN], head, tail;
int match[MAXN + 1], father[MAXN + 1], base[MAXN + 1];
void init(int _n)
{
n = _n;
for (int i = 1; i <= n; ++i)
{
match[i] = 0;
for (int j = 1; j <= n; ++j)
mat[i][j] = false;
}
}
int pop()
{
return que[head++];
}
void push(int x)
{
que[tail++] = x;
inque[x] = true;
}
void add_edge(int a, int b)
{
mat[a][b] = mat[b][a] = true;
}
int inpath[MAXN + 1];
static int pcnt;
int find_ancestor(int u, int v)
{
++pcnt;
while (u)
{
u = base[u];
inpath[u] = pcnt;
u = father[match[u]];
}
while (true)
{
v = base[v];
if (inpath[v] == pcnt)
return v;
v = father[match[v]];
}
}
int inblossom[MAXN + 1];
static int bcnt;
void reset(int u, int anc)
{
while (u != anc)
{
int v = match[u];
inblossom[base[v]] = bcnt;
inblossom[base[u]] = bcnt;
v = father[v];
if (base[v] != anc) father[v] = match[u];
u = v;
}
}
void contract(int u, int v)
{
int anc = find_ancestor(u, v);
++bcnt;
reset(u, anc);
reset(v, anc);
if (base[u] != anc) father[u] = v;
if (base[v] != anc) father[v] = u;
for (int i = 1; i <= n; ++i)
if (inblossom[base[i]] == bcnt)
{
base[i] = anc;
if (!inque[i]) push(i);
}
}
int find_augment(int start)
{
for (int i = 1; i <= n; ++i)
{
father[i] = 0;
inque[i] = false;
base[i] = i;
}
head = 0, tail = 0, push(start);
while (head < tail)
{
int u = pop();
for (int v = 1; v <= n; ++v)
if (mat[u][v] && base[v] != base[u] && match[v] != u)
{
if (v == start || (match[v] && father[match[v]]))
contract(u, v);
else
{
if (father[v] == 0)
{
if (match[v])
{
push(match[v]);
father[v] = u;
}
else
{
father[v] = u;
return v;
}
}
}
}
}
return 0;
}
void augment(int finish)
{
int u = finish, v, w;
while (u)
{
v = father[u];
w = match[v];
match[u] = v;
match[v] = u;
u = w;
}
}
int graph_max_match()
{
int ans = 0;
for (int i = 1; i <= n; ++i)
if (match[i] == 0)
{
int finish = find_augment(i);
if (finish)
{
augment(finish);
ans += 2;
}
}
return ans;
}
} g;
int Graph :: bcnt = 0, Graph :: pcnt = 0;
int dis(int i, int j, int l)
{
int d;
d = abs(x[i] - x[j]) + abs(y[i] - y[j]);
if (d <= l) return 1;
else return 0;
}
int main()
{
int n;
while (scanf("%d", &n) != EOF)
{
int l;
g.init(n);
for (int i = 1; i <= n; ++i)
scanf("%d%d", &x[i], &y[i]);
scanf("%d", &l);
for (int i = 1; i < n; ++i)
for (int j = i + 1; j <= n; ++j)
{
if (dis(i, j, l)) g.add_edge(i, j);
}
int sum;
sum = g.graph_max_match();
if (sum == n) puts("YES");
else puts("NO");
}
return 0;
}