题解 P7368

Silence_water · 2021-03-03 14:53:26 · 题解

题目传送门

二分图最小覆盖的模型特点是：每条边有 2 个端点，二者至少选择一个。我们不妨称之为 "2 要素"。

——李煜东《算法竞赛进阶指南》

我们来寻找一下本题的 "2 要素"：

每个小行星可以通过本行的武器或每列的武器被消除，二者至少选择一个。

我们将每个小行星的 x 坐标与 y 坐标看成一条边的两个端点。那么形成的这张图中的任意一条边都需要有至少一个端点有武器摆放。

换句话说，问题就是要求出一个最小的点集 S，使得图中任意一条边都有至少一个端点属于 S。这个问题被称为二分图的最小点覆盖。

故求消除所有小行星的最小代价就相当于求这张二分图的最小点覆盖数。

根据 König 定理，二分图最小点覆盖包含的点数等于二分图最大匹配包含的边数。

直接用匈牙利算法跑即可。

bool dfs(int u)
{
    for(int i=1;i<=n;i++)
    {
        if(!e[u][i]||vis[i])continue;
        vis[i]=true;
        if(!match[i]||dfs(match[i]))
        {
            match[i]=u;
            return true;
        }
    }
    return false;
}
int solve()
{
    memset(match,0,sizeof(match));
    int cnt=0;
    for(int i=1;i<=n;i++)
    {
        memset(vis,false,sizeof(vis));
        if(dfs(i))cnt++;
    }
    return cnt;
}

upd 2023/1/3：根据评论区反馈修正了错误。