bzoj 2044 三维导弹拦截 —— 最小路径覆盖

题目：https://www.lydsy.com/JudgeOnline/problem.php?id=2044

第一问暴力 n^2 即可；

注意这道题对位置没要求！所以先按第一维排序一下即可；

然后拆入点和出点，求一个最小路径覆盖即可。

代码如下：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

int const maxn=;

int n,f[maxn],ans,mx,hd[maxn],ct,to[maxn*maxn],nxt[maxn*maxn],pre[maxn];

bool vis[maxn];

struct N{int x,y,z;}p[maxn];

void add(int x,int y){to[++ct]=y; nxt[ct]=hd[x]; hd[x]=ct;}

bool cmp(N a,N b){return a.x<b.x;}

bool dfs(int x)

{

    for(int i=hd[x],u;i;i=nxt[i])

    {

        if(vis[u=to[i]])continue;

        vis[u]=;

        if(!pre[u]||dfs(pre[u])){pre[u]=x; return ;}

    }

    return ;

}

int main()

{

    scanf("%d",&n);

    for(int i=;i<=n;i++)scanf("%d%d%d",&p[i].x,&p[i].y,&p[i].z);

    sort(p+,p+n+,cmp);

    for(int i=;i<=n;i++)

    {

        f[i]=;

        for(int j=;j<i;j++)

            if(p[j].x<p[i].x&&p[j].y<p[i].y&&p[j].z<p[i].z)//p[i].x!=p[j].x!

            {

                f[i]=max(f[i],f[j]+);

                add(j,i);//j -> i

            }

        mx=max(mx,f[i]);

    }

    for(int i=;i<=n;i++)

    {

        memset(vis,,sizeof vis);

        if(dfs(i))ans++;

    }

    ans=n-ans;

    printf("%d\n%d\n",mx,ans);

    return ;

}