题解：P8694 [蓝桥杯 2019 国 AC] 估计人数

Rem_CandleFire · 2024-09-02 15:51:23 · 题解

分析与做法

若将矩阵上的 1 看做一个有向图，那么问题能转化成有向图上的最小可重链覆盖。

套路地，对于有向图做一个传递闭包（人话就是预处理出任意两点是否可达），这样我们就可以在上面做最小不可重链覆盖。

继续套路，将每个点拆成入点和出点，对于有向图上的一对可互相到达的点 (u,v)，连边 u_{out} 和 v_{in}，那么二分图每一条边就对应着原图的某条边。

那么根据 Dilworth 定理 以及该文中的一些推理，答案就是有向图点数减去最大匹配。那么此题就做完了。

Code

#include<bits/stdc++.h>
using namespace std;
const int N=1005;
int n,m,len;
int f[N][N],mch[N],vis[N];
struct node{ int x,y; } p[N];
vector<int> g[N];
void Add(int u,int v){ g[u].push_back(v),g[v].push_back(u); }
bool Match(int u)
{
    for(auto v:g[u])
    {
        if(vis[v]) continue;
        vis[v]=1;
        if(!mch[v]||Match(mch[v]))
            { mch[v]=u; return true; }
    }
    return false;
}
int main()
{
    scanf("%d%d",&n,&m); char c;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            cin>>c;
            if(c=='1') p[++len]={i,j};
        }
    for(int i=1;i<=len;i++)
        for(int j=i+1;j<=len;j++)
            if(p[i].x==p[j].x&&p[i].y+1==p[j].y||p[i].x+1==p[j].x&&p[i].y==p[j].y) f[i][j]=1;
    for(int k=1;k<=len;k++)
        for(int i=1;i<=len;i++)
            for(int j=1;j<=len;j++)
                f[i][j]|=(f[i][k]&f[k][j]);
    for(int i=1;i<=len;i++)
    {
        for(int j=i+1;j<=len;j++)
            if(f[i][j]) Add(i,j+len);
    }
    int sum=0;
    for(int i=1;i<=len;i++)
    {
        fill(vis,vis+1+len*2,0);
        if(Match(i)) sum++;
    }
    printf("%d",len-sum);

    return 0;
}