从 P11816 初学 Hall 定理和轮廓线 dp

· · 题解

知识点：Hall 定理、轮廓线 dp。

赛时被队友一眼秒了但是自己不会怎么办。

本文内棋子可以移动的方向和题目里的相反。

我们把初始状态的每个棋子看作一个左部点，最终状态的每个棋子看作一个右部点。

在可以到达的状态之间连边，本题就是在求这个二分图是否存在完备匹配。

根据 Hall 定理，一个二分图存在完备匹配的充要条件是对于左部点的大小为 k 的任意子集 S，这些点在右部连到的点集大小不小于 k。

所以我们令 c_{i,j,k}=a_{i,j,k}-b_{i,j,k}，我们要求的就是以下问题。

选取若干个点，如果有一个点被某个选择的点偏序了那么这个点也要选。使得选出的点的权值 c 之和最大。

如果这个最大值大于 0，就说明存在一个点集不满足上述条件。

设 p_{i,j} 表示第 i 块第 j 行选了前 p_{i,j} 个点。根据偏序关系容易有 p_{i,j}\geq p_{i,j+1} 和 p_{i,j}\geq p_{i+1,j}。

因为后两维的数据范围很小，考虑直接把他们压缩在一起。状态数的计算考虑组合意义，即 C_{6+6}^{6}=924。

有第一种状态 f_{i,w} 表示考虑到第 i 层且第 i 层选点状态是 w，权值和的最大值。

直接暴力转移是 O(n\times 924^2) 的，大抵是过不去。

怎么办？可以考虑轮廓线 dp。

假如轮廓线现在的状态长这样： p_{i,j} 1 2 3 4 5 6
j-1 / / / ? 1 0
j 6 3 3 2 / /

那么我们枚举问号处选中了多少个点，就可以从上一个轮廓线的状态转移。

还是因为偏序关系，这里轮廓线的总状态数顶天是 6\times 924 的，加上转移复杂度仍然是可以过的。

实现时建议开滚动数组，以及特判 B=1 时带来的一些问题。

代码前面几行也是简要的题解。

//学习Hall定理和轮廓线dp。 
//首先每个棋子看成一个点 a是左部点b是右部点
//能移动到的连边 这题就是在求是否有完备匹配
//Hall定理：一个图存在完备匹配的充要条件是
//          对于任意大小为k的左部点集S，它的可达右部点集T大小>=k
//那么令c[i][j][k]=a[i][j][k]-b[i][j][k]
//我们要选择一些点(如果一个点选了那么被偏序的必须选)
//使得sum(c[i][j][k])最大。
//其他两维很小，考虑直接压缩状态 
// #####. 首先对于一层的点的选择状态肯定长这样。 
// #####. 考虑直接把第三维压掉变成二维问题。 
// ####.. 从上往下转移，每层选的点数肯定也和上一层偏序。 
// ####.. 然后转移是一个高维前缀max 但是不好做 实际上和状压差不多 
// ##.... 我们考虑轮廓线dp！
//        假如轮廓线现在长这样（存储为f[4][6,3,3,2,1,0]） 
// ...?10 那么我们只需要枚举?位置的值就可以从f[3][6,3,3,?,1,0]转移过来了
// 6332   用组合意义粗略估算有效状态数约为C(12,6)*6=5544。轻微卡常。 
#include<bits/stdc++.h>
#define MX 10005
#define int long long
#define CKE if(CHECK)
#define FRE if(FIL)
using namespace std;
const int CHECK=0,FIL=0;int read();
int T,n,x,y,cnt,a[MX][7][7],b[MX][1000];
int f[117649],p[1000][8],q[7],g[7][1000]; 
void dfs(int t,int lst,int o){
    if(t>x){
        p[++cnt][0]=o;f[o]=cnt;
        for(int i=1;i<=x;i++)
            p[cnt][i]=q[i];
        p[cnt][x+1]=0;
        return;
    }
    for(int i=0;i<=lst;i++){
        q[t]=i;dfs(t+1,i,o*(y+1)+i);}
}
signed main(){
    //ios::sync_with_stdio(false);
    //cin.tie(0);cout.tie(0);
    FRE freopen(".in","r",stdin);
    FRE freopen(".out","w",stdout);
    T=read();while(T--){
        n=read();x=read();y=read(); 
        for(int i=n;i>=1;i--) for(int j=x;j>=1;j--) for(int k=y;k>=1;k--)
            a[i][j][k]=read();
        for(int i=n;i>=1;i--) for(int j=x;j>=1;j--) for(int k=y;k>=1;k--)
            a[i][j][k]-=read();
        //搜索所有可能状态 & 其他预处理 
        //p[t][0] 第t个状态hash值
        //p[t][1~x] 第t个状态代表什么
        //f[h] hash值为h的是哪个状态
        //b[i][t] 第i层 第t个状态覆盖的点的权值和 
        cnt=0;dfs(1,y,0);
        memset(g[0],-0x3f,sizeof(g[0]));
        g[0][1]=0,q[x]=1;
        for(int i=x-1;i>=0;i--) q[i]=q[i+1]*(y+1);
        for(int i=1;i<=n;i++){
            for(int j=1;j<=cnt;j++){
                b[i][j]=0;
                for(int k=1;k<=x;k++) for(int l=1;l<=p[j][k];l++)
                    b[i][j]+=a[i][k][l];
            }
        }
        //轮廓线 dp
        int res=0;
        for(int t=n;t>=1;t--){
            for(int o=1;o<=x;o++){
                for(int I=1;I<=cnt;I++){
                    //第t块
                    //轮廓线包含第t块前o个和第t-1块的后B-o个状态 
                    //这些状态叠起来是第I个状态 
                    int lo=p[I][o+1];
                    int hi=p[I][o];
                    int zt=p[I][0]-q[o]*hi;
                    if(x>1) g[o%x][I]=-1e18;
                    for(int i=lo;i<=hi;i++)
                        g[o%x][I]=max(g[o%x][I],g[o-1][f[zt+q[o]*i]]);
                }
            }
            //这一层枚举完了 加上对应权值 
            for(int I=1;I<=cnt;I++){
                g[0][I]+=b[t][I];
                if(t==1) res=max(res,g[0][I]);
            }
        }
        if(res>0) printf("NIE\n");
        else printf("TAK\n");
    }
    return 0;
}
int read(){
    int Ca=0;char Cr=' ';int Cf=1;
    while(Cr<'0' || Cr>'9'){Cr=getchar();if(Cr=='-'){Cf=-1;}}
    while(Cr>='0' && Cr<='9'){Ca=Ca*10+Cr-48;Cr=getchar();}
    return Ca*Cf;
}