关键词:  Dilworth定理  数学-数论  数学-组合 相关题目:导弹拦截 [Neerc2009]Exclusive Access 2 [CTSC] 祭祀 Medium:IncubatorEasy

最长反链与最小链覆盖

    大前提:在有向无环图中

    链是一个点的集合,这个集合中任意两个元素v、u,要么v能走到u,要么u能走到v。     反链是一个点的集合,这个集合中任意两点谁也不能走到谁。     最长反链是反链中最长的那个。

    那么最长反链怎么求呢?

    另一个东西叫:最小链覆盖。就是用最少的链,经过所有的点至少一次(为什么不叫最少链覆盖啊囧……)     于是Dilworth定理来了:最长反链长度 = 最小链覆盖数     下面来证明:

    首先,最长反链中的每个点,一定在不同的链中,所以得到:最长反链长度 ≤ 最小链覆盖数     下面关心的是,最长反链长度 ≥ 最小链覆盖数吗?     用数学归纳法。     首先空的图显然成立。     假设对于所有点数小于图G的图都成立,现在来证G也满足条件。

    两个定义:源:没有一个点能走到它的点。(入度为0) 汇:不能走到任何一个点的点。(出度为0)     设:     这个图点集为V     这个图的最长反链为A     能走到A中某个点的点的集合为B,A中某个点能走到的点构成的集合为C。

  1. 若A中至少有一个点既不是源也不是汇则:

    1. B ≠ V (否则反链的点全是汇)
    2. C ≠ V (否则反链的点全是源)
    3. B ∪ C = V:反证法,假设有一个点v既不属于B也不属于C,那么说明反链上任何一点不能到v,v也不能到反链上任何一个点,反链加上v之后能成为更长的反链,与假设矛盾。
    4. B ∩ C = A:反证法,假设有一个点v既属于B也属于C但不属于A,那么说明反链上某点a能到v,v能到反链上某点b。若a = b,则与图是有向无环图矛盾。若a ≠ b,则a能先到v,在从v到达b,与a、b都在反链上矛盾。

    设B构成的子图、C构成的子图的最小链覆盖的链的集合分别为C[B]和C[C]。因为|B| < |V|,|C| < |V|,由归纳假设,C[B]、C[C]大小分别等于B构成的子图和C构成的子图的最长反链的大小。 考虑一条链c ∈ C[B],则c中必然存在一个在最长反链上的点v,不然最小链覆盖会大于最长反链,与归纳假设矛盾。因为B ∩ C = A,所以C[B]中v不能到任何一个点。所以v必为c的汇。 于是得到:A中的点都是C[B]中某条链的汇同理:A中的点都是C[C]中某条链的源。 又B ∪ C = V,B ∩ C = A,C[B]中某条链的汇必为C[C]中某条链的源,于是把C[B]和C[C]拼起来,就得到一个原图G的一种可行的链覆盖了! 考虑这个链覆盖,发现这个链覆盖大小 = 最长反链长度,得到最小链覆盖大小 ≤ 最长反链长度。又由前面的最小链覆盖大小 ≥ 最长反链长度,所以G中最小链覆盖大小 = 最长反链长度

  2. 若A是所有源的集合或所有汇的集合 若A是所有源的集合,那么从A中随便取一个元素v(这个可以随便找到吧) 再从V中随便找一个汇u,使得v可以到u(这个也可以随便找到吧)(u可以等于v) 然后G中去掉v、u形成图G'。则G'的最长反链大小一定小于等于|A| - 1,不然的就可以在G中找到一条不选v、u的最长反链,利用(1)的结论可以证明正确性。 由于归纳假设,则G'中一定可以找到一个数量为|A| - 1的链覆盖。再加上{v} ∪ {u}这条链,则可以在G中找到一个数量为|A|的链覆盖,所以G的最小链覆盖 ≤ 最长反链长度。 又由前面的最小链覆盖大小 ≥ 最长反链长度,所以G中最小链覆盖大小 = 最长反链长度。

    证完了,这就是传说中的Dilworth定理:最小链覆盖数 = 最长反链长度。     其对偶定理:最长链长度 = 最小反链覆盖数 就不证了,网上的证明烂大街了。

    那么求最小链覆盖数的方法,就是首先传递闭包,然后就变成了最小路径覆盖。拆点,用二分图匹配解决之。这是后话,不说了。

    应用:     NOIP 1999 导弹拦截     CTSC2008 祭祀    

参考资料:《2008 全国信息学奥林匹克年鉴》 讲解来源:最长反链与最小链覆盖

导弹拦截

题目描述

    某国为了防御敌国的导弹袭击,发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷:虽然它的第一发炮弹能够到达任意的高度,但是以后每一发炮弹都不能高于前一发的高度。某天,雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段,所以只有一套系统,因此有可能不能拦截所有的导弹。     输入导弹依次飞来的高度(雷达给出的高度数据是不大于50000的正整数),计算这套系统最多能拦截多少导弹,如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。

输入输出格式

输入格式:     一行,若干个整数(个数少于100000)

输出格式:   2行,每行一个整数,第一个数字表示这套系统最多能拦截多少导弹,第二个数字表示如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
int n=0,a[100001],f[100001],d[100001],ans=1,t=0;
int main() {
while(~scanf("%d",&a[++n]));//读入数据方法
n--;//n是导弹数,由于某些原因要--
for(int i=1; i<=n; i++) {
f[i]=1;
for(int j=t; j>0; j--)
if(a[i]<=a[d[j]]) {
f[i]=f[d[j]]+1;
break;
}
t=max(t,f[i]);
d[f[i]]=i;//简单的维护过程
ans=max(ans,f[i]);
}
printf("%d\n",ans);
ans=1;
t=0;
for(int i=1; i<=n; i++) {
f[i]=1;
for(int j=t; j>0; j--)
if(a[i]>a[d[j]]) {
f[i]=f[d[j]]+1;
break;
}
t=max(t,f[i]);
d[f[i]]=i;
ans=max(ans,f[i]);
}
printf("%d",ans);
}

来自洛谷用户:c201904

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include<cstdio>
#include<string.h>
#include<iostream>
using namespace std;
const int maxn=100005;
int a[maxn];
int f[maxn];
int main()
{
int n=0;
int l,r,mid;
while(scanf("%d",&a[++n])!=EOF)continue;
n--;
f[0]=1234123412;//这个数要大于50000,不然可能你就无法更新
int ans1=0;
for(int i=1;i<=n;i++){
if(f[ans1]>=a[i]){
f[ans1+1]=a[i];//结束点为a[i]
ans1++; //当前最长不上升序列的长度加一
}
else {//二分查找
l=0;r=ans1;
while(l<r){
mid=(l+r)/2;
if(f[mid]>=a[i])l=mid+1;
else {
r=mid;
}
}
if(l!=0)f[l]=a[i];
}
}
cout<<ans1<<endl;//输出第一问的答案
memset(f,-1,sizeof(f));//这次前面要尽量小了,不然又无法更新
int ans2=0;
for(int i=1;i<=n;i++){
if(f[ans2]<a[i]){
f[ans2+1]=a[i];//结束点为a[i]
ans2++; //当前最长上升序列长度加一
}
else {//二分查找
l=0;r=ans2;
while(l<r){
mid=(l+r)/2;
if(f[mid]>=a[i])r=mid;
else {
l=mid+1;
}
}
f[l]=a[i];
}
}
cout<<ans2<<endl;//输出第二个答案
}

来自洛谷用户:cplusplus