3D导弹拦截

题目简述

「导弹拦截」这道题相信大家都已经做过了，现在这道题就是三维板的「导弹拦截」。

具体来讲，每发导弹有三个参数 $x,y,z$，所有导弹的三个参数各不相同。导弹拦截系统第一次可以拦截任意的一个导弹吗，但是之后拦截的导弹三个参数必须都大于第一次拦截的导弹。问这套系统最多可以拦截多少导弹，要拦截所有的导弹至少需要部署多少个这样的系统？

思路

第一问很容易做，无非就是多了两个参数 —— 可以在 $n^{2}$ 时间里 DP 求得。

关键是第二问：考虑从导弹拦截的顺序下手，如果系统在拦截导弹 $i$ 之后还可以继续拦截导弹 $j$，那么我们就连一条 $i$ 到 $j$ 的有向边，最终我们会得到一个图 —— 显然这是个 DAG（有向无环图）。我们可以发现系统可以拦截的导弹以及拦截顺序其实就是图上的简单路径，那么要用最少数量的导弹拦截系统拦截所有的导弹就是用最少的简单路径覆盖图上的所有点 —— 也就是求最小路径点覆盖。

最小路径点覆盖的求解

给定一张有向无环图，要求用尽量少的不相交简单路径覆盖图上所有点（即每个点恰好被覆盖一次），这个问题就是有向无环图上的「最小路径点覆盖」（或「最小路径覆盖」）。

拆点二分图：

设原来的 DAG 为 $G=(V,E),n=|V|$，把 $G$ 中的每个顶点 $x$ 拆成 $x_{o},x_{i}$ 两个点，建立一张新的二分图，其中 $o$ 类点作为左部点，$i$ 类点作为右部点。对于原图中的每条有向边 $(x,y)$，在左部点 $x_{o}$ 和右部点 $y_{i}$ 间连边 $(x_{o},y_{i})$，最终得到的二分图称为原图 $G$ 的拆点二分图，记为 $G_{2}$。

定理：

有向无环图 $G$ 的最小路径点覆盖包含的路径条数，等于原图点数 $n$ 减去其拆点二分图 $G_{2}$ 的最大匹配数。

证明：

最小路径点覆盖中 $G$ 的每一点都恰好被覆盖一次，即其入度和出度有且仅有一个是 $1$。于是原图最小路径点覆盖的所有边在其拆点二分图 $G_{2}$ 中构成一组匹配 —— 每条边的起点 $x$ 于拆点二分图中匹配边左部点 $x_{o}$ 一一对应。对于每条路径的终点 $t$，由于其没有出边，所以在二分图中 $t_{o}$ 失配，于是原图每条路径的终点与拆点二分图失配的左部点一一对应。

最小路径覆盖中要求包含路径最少，即路径终点数最少，即在拆点二分图中左部非匹配点最少，即匹配点最多。于是最小路径点覆盖的路径条数等于原图点数 $n$ 减去其拆点二分图 $G_{2}$ 的最大匹配数。

狄尔沃斯定理于本题的不适用性

偏序集：

现有集合 $P$，$P$ 上的二元关系 $≤$（不是小于，只是一种二元关系，使用了这个符号而已）满足以下三个条件，则称 $≤$ 是 $P$ 上的偏序关系

自反性：$∀a∈P,\ a≤a$
反对称性：$∀a,b∈P,\ 若 \ a≤b \ 且 \ b≤a, \ 则 \ a=b$
传递性：$∀a,b,c∈P,\ 若\ a≤b\ 且\ b≤c,\ 则\ a≤c$

具有偏序关系的集合 $P$ 为偏序集（或称半序集），记为 $(P, ≤)$

狄尔沃斯定理：

对于任意有限偏序集，其最大反链中元素的数目必等于最小链划分中链的数目，其最长链中元素的数目必等于其最小反链划分中反链的数目。

于「导弹拦截」的适用性：

还记得这道题中的两个答案就是最长不升子序列和最长上升子序列的长度吗？

虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。

「导弹拦截」一题中，导弹构成的集合中有偏序关系「高度小于等于」，具体来讲，「高度小于等于」的关系满足：

任意一颗导弹，其高度小于等于自己的高度（自反性）
两颗导弹 $a,b$，$a$ 的高度小于等于 $b$ 的高度，$b$ 的高度小于等于 $a$ 的高度，那么两颗导弹高度相等（反对称性）
三颗导弹 $a,b,c$，$a$ 的高度小于等于 $b$ 的高度，$b$ 的高度小于等于 $c$ 的高度，那么 $a$ 的高度小于等于 $c$ 的高度(传递性)

于是狄尔沃斯定理适用于这道题

于本题中的不适用性：

为什么这道题中我们不使用狄尔沃斯定理，而是要使用上面所讲的比较麻烦的方法呢？

虽然它的第一发炮弹能够到达三维空间中任意的点，但是以后每一发炮弹到达点的坐标 (x,y,z) 的三个坐标值都必须大于前一发炮弹的对应坐标值。

本题中导弹构成的集合具有关系「每个坐标值都大于」，不满足自反性 —— 因为对于任意一个导弹，其每个坐标值都等于它自己，不具有「每个坐标值都大于」的关系，故「每个坐标值都大于」不是偏序关系，导弹构成的集合不是偏序集，无法使用狄尔沃斯定理求解。

如果将本题中「每个坐标值都大于」改为「每个坐标值都不小于」，那么导弹构成了一个偏序集，我们就可以直接在 DP 转移时实时更新答案了。

Code

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<climits>
#define int long long
using namespace std;
const int MaxN = 1003;
int n, f[MaxN], ans, cnt, head[MaxN*MaxN], cntEdge, from[MaxN];
bool visited[MaxN*2];
struct Edge{
	int destination, nextEdge;
}edge[MaxN*MaxN];

struct Missile{
	int x, y, z;
	bool operator < (const Missile &a) const{
		return x < a.x;
	}
}missile[MaxN*MaxN];

inline int Read(){
	int num = 0, op = 1;
	char ch = getchar();
	while(!isdigit(ch)){
		if(ch == '-') op = -1;
		ch = getchar();
	}
	while(isdigit(ch)){
		num = num * 10 + ch - '0';
		ch = getchar();
	}
	return num * op;
}

inline void AddEdge(int u, int v){
	cntEdge++;
	edge[cntEdge].destination = v;
	edge[cntEdge].nextEdge = head[u];
	head[u] = cntEdge;
	return;
}

inline bool DFS(int x){
	for(int i = head[x]; i; i = edge[i].nextEdge){
		int y = edge[i].destination;
		if(visited[y]) continue;
		visited[y] = true;
		if(!from[y] || DFS(from[y])){
			from[y] = x;
			return true;
		}
	}
	return false;
}

signed main(){
	n = Read();
	for(int i=1; i<=n; i++)
		missile[i] = (Missile){Read(), Read(), Read()};
	sort(missile+1, missile+1+n);
	for(int i=1; i<=n; i++)
		for(int j=1; j<=n; j++)
			if(missile[i].x < missile[j].x && missile[i].y < missile[j].y && missile[i].z < missile[j].z){
				f[j] = max(f[j], f[i]+1);
				ans = max(ans, f[j]);
				AddEdge(j, i);
			}
	for(int i=1; i<=n; i++){
		memset(visited, false, sizeof(visited));
		if(DFS(i)) cnt++;
	}
	ans = ans + 1;
	printf("%lld\n%lld\n", ans, n-cnt);
	return 0;
}