爆破VS凤凰

题目链接：http://acm.ocrosoft.com/problem.php?cid=1629&pid=53

题目描述：

Er-pang又跟生哥去网吧打LOL（英雄联盟），er-pang还是用他最爱的爆破鬼才-吉格斯，生哥还是用他花重金买下的冰晶凤凰-艾尼维亚。每次生哥都被虐的很惨。

生哥终于忍不住了，他居然开挂了！

开了挂后的凤凰越飞越高，居然还出现了n-1个幻象（逆天了），加上本尊一共n个凤凰在天上乱飞。由于爆破鬼才的视力极好，可以在瞬间扔出炸弹并炸死凤凰或是幻象。所以我们可以看做三维立体空间中有n个不动的凤凰，每个凤凰有一个坐标（x，y，z）。爆破鬼才的炸弹爆炸后不会消失，而且还会跳跃，但仅能跳到更高的地方。即如果炸弹当前处在（x1，y1，z1），当且仅当x2>x1，y2>y1，z2>z1时，它会跳到（x2，y2，z2）。

举个例子：凤凰在（0，0，0）（1，1，0）（1，1，1）（2，2，2）时

一个合法的炸弹弹跳序列是{1,3,4}

一个不合法的炸弹弹跳序列是{1,2,4}

现在告诉你n个凤凰的精确位置，问你两个问题：

1. 爆破鬼才扔出一个炸弹最少能炸死多少凤凰

2. 爆破鬼才至少需要扔出多少个炸弹才能将凤凰全部炸死

输入

第一行一个整数为n，表示天空中有n个凤凰。

接下来的n行每行有三个非负整数xi，yi，zi表示凤凰的位置，保证任意两个凤凰不会出现在同一位置。

输出

输出文件有且仅有两行。

第一行输出一个整数表示一个炸弹最多能炸死多少个凤凰

第二行输出一个整数表示至少需要多少个炸弹才能炸死全部的凤凰

样例输入

样例输出

3
2

提示
所有坐标都是0~1000000的整数
30%    n<=30
50%    n<=100
100%   n<=1000

思路：

其实就是导弹拦截的三维版。第一问求最长上升子序列，先将数据按x的大小升序排列，然后求答案。第二问：能从自己转移到哪些状态就从自己向哪些状态连边，然后就是最小路径覆盖了。用二分图的 n-最大匹配

代码：

#include<bits/stdc++.h>
using namespace std;
int n,f[1010],ans=0;
int es[1000010],enx[1000010],e0[2010],ed[2010],nx[2010],now=1,ep=2;
struct pos
{
    int x,y,z;
} ps[1010];
bool cmp(pos a,pos b)
{
    return a.x<b.x;
}
bool operator<(pos a,pos b)
{
    return a.x<b.x&&a.y<b.y&&a.z<b.z;
};
void adde(int a,int b)
{
    es[ep]=b;
    enx[ep]=e0[a];
    e0[a]=ep++;
    es[ep]=a;
    enx[ep]=e0[b];
    e0[b]=ep++;
}
bool dfs(int w)
{
    ed[w]=now;
    if(nx[w]&&ed[nx[w]]!=now) return dfs(nx[w]);
    for(int i=e0[w];i;i=enx[i])
    {
        int u=es[i];
        if(ed[u]==now)
            continue;
        if(!nx[u]||dfs(u))
        {
            nx[w]=u;
            nx[u]=w;
            return 1;
        }
    }
    return 0;
}
int main()
{
    scanf("%d",&n);
    for(int i=0;i<n;i++) scanf("%d%d%d",&ps[i].x,&ps[i].y,&ps[i].z);
    sort(ps,ps+n,cmp);//按x进行升序排序
    //第一问
    for(int i=0;i<n;i++)
    {
        f[i]=1;
        for(int j=0;j<i;j++)
            if(ps[j]<ps[i])
            {
                if(f[i]<f[j]+1) f[i]=f[j]+1;
                adde(i,j+n);
            }
        if(ans<f[i]) ans=f[i];
    }
    printf("%d\n",ans);
    //第二问
    ans=n;
    for(int i=1;i<=n;i++,now++)
        if(!nx[i]) ans-=dfs(i);
    printf("%d\n",ans);
    return 0;
}