SP9761 SCPC11H - Dolls 题解

一E孤行 · 2021-08-09 11:28:29 · 题解

SCPC11H - Dolls 题解

做法分析

套娃/套矩阵，是很经典的最小路径覆盖（二分图）模型。

如果一个套娃能完全套在另一个套娃里面（其长宽高均小于另一个）这样我们把大套娃向小套娃连边。

每一组套完的套娃，都可以对应到图上的一条路径（可以只是个单点，就是啥也没法套，一个点也可以看作一条路径）而每个套娃只能套一次，说明每一个点就只能在一条路径里出现。

这就显而易见了，是一个最小路径覆盖（一定是有向无环图，如果不是则说明有套娃的大小出现歧义，很好理解）

算法分析

那么 DAG 的最小路径覆盖怎么做呢？我们把原图中的每个点拆成 2 个点，如果原图中有一条边 (u,v)，我们连一条 u 的左边点到 v 的右边点的有向边，这样连完后，整个图会成为一个二分图。最后的答案就是点数减去二分图最大匹配。

AC Code

#include<cstdio>
#include<algorithm>
#include<queue>
#include<iostream>
#include<cstring>
#include<ctime>
using namespace std;
#define maxn 1005
#define inf 1000000000
int n,s,t;
struct bbb{
    int x,y,z;
}b[20*maxn];
struct aaa{
    int to,next,c;
}a[maxn*maxn*10];
int head[maxn],tot,d[maxn*20];
void init() {
    memset(head,-1,sizeof(head));
    tot=0;
}
bool bfs() {
    queue<int> q;
    q.push(s);
    memset(d,-1,sizeof(d));
    d[s]=0;
    while(!q.empty()) {
    //    printf("qwq\n");
        int u=q.front();
        q.pop();
        for(int i=head[u];~i;i=a[i].next) {
            int v=a[i].to;
            if(d[v]==-1&&a[i].c) {
                d[v]=d[u]+1;
                q.push(v);
            }
        }
    }
    return d[t]!=-1;
}
int dfs(int u,int flow) {
    if(u==t)
        return flow;
    int res=0;
    for(int i=head[u];~i;i=a[i].next) {
        int v=a[i].to;
        if(a[i].c&&d[v]==d[u]+1) {
            int tmp=dfs(v,min(flow,a[i].c));
            flow-=tmp;
            res+=tmp;
            a[i].c-=tmp;
            a[i^1].c+=tmp;
            if(!flow)
                break;
        }
    }
    if(!res)
       d[u]=-1;
    return res;
}
int Dinic() {
    int res=0;
    while(bfs())
        res+=dfs(s,inf);
    return res;
}
void add(int x,int y,int c) {
    a[tot].to=y;
    a[tot].c=c;
    a[tot].next=head[x];
    head[x]=tot++;
}
int main() {
    clock_t c1=clock();
#ifdef LOCAL
    freopen("in.in","r",stdin);
    freopen("out.out","w",stdout);
#endif
    //=========================================
    while(scanf("%d",&n),n) {
        init();
        for(int i=1;i<=n;i++)
            scanf("%d%d%d",&b[i].x,&b[i].y,&b[i].z);
        s=0,t=2*n+2;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                if(b[i].x>b[j].x&&b[i].y>b[j].y&&b[i].z>b[j].z)
                    add(i,j+n,1),add(j+n,i,0);
        for(int i=1;i<=n;i++)
            add(s,i,1),add(i,s,0);
        for(int i=1;i<=n;i++)
            add(i+n,t,1),add(t,i+n,0);
        printf("%d\n",n-Dinic());
    }
    //=========================================
end:
    cerr<<"Tmie Used:"<<clock()-c1<<"ms"<<endl;
    return 0;
}