ABC 446 F 题解

· · 题解

前言

五年级蒟蒻第二次切 F（虽然是赛后）。这道题不难吧，这么简单的。没有场切可惜了。

题目大意

给定一个有向图，有 n 个顶点和 m 条边。对于每个 k=1,2,\ldots,n，我们需要判断：

能否删除一些顶点（同时删除与之相连的边），使得从 1 出发能到达的顶点集合恰好是 {1,2,\ldots,k}。

如果能，输出最少需要删除多少个顶点。

如果不能，输出 -1。

解题思路

对于固定的 k，要求从 1 出发能到达的顶点恰好是 1 \sim k，这也就说明：

因此，我们需要删除那些会让我们到达 >k 的顶点的关键顶点，这些顶点一旦保留，就会导致从 1 能到达不该到达的顶点。

同时我们发现，如果我们从小到大处理 k，会发现一些性质：

解决流程

我们可以使用 BFS 加上优先队列来一起模拟解决这道题目：

  1. 从顶点 1 开始搜索，并用优先队列（这里使用小根堆）来存储当前可以到达的顶点。
  2. 我们可以维护一个变量 ans 表示已经确定可以到达的顶点中，编号 \le i 的有多少个。
  3. 对于每个 i 从 1 到 n：
    • 弹出所有编号 \le i 的可以到达的顶点。（这些顶点现在确定一定可以到达）
    • 每弹出一个顶点，ans+1，并把它能到达的未访问的相邻结点加入优先队列。
    • 检查：如果 ans < i，说明有某个 j \le i 的顶点无法到达，则直接输出 -1。
    • 否则，优先队列中剩下的就是编号 >i 但可以到达的顶点，这些顶点就需要删除，因此所以输出队列大小。

这样我们整个题目就做完了。不过这里我来解释一下为什么队列大小就是最少删除数？

为什么队列大小就是最少删除数？

因为优先队列中存储的是当前可以到达的、编号 >i 的顶点。这里也应该看得出来了。因此我们需要删除的结点数就是我们优先队列的大小。

AC 代码

代码十分简单，上面也讲得十分详细了，则不写注释。

#include<bits/stdc++.h>
using namespace std;
const int N=3e5+10;
vector<int> g[N];
int n,m;
bool vis[N];
int ans;
priority_queue<int,vector<int>,greater<int>> q;
int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int u,v;
        cin>>u>>v;
        g[u].push_back(v);
    }
    q.push(1);
    vis[1]=1;
    for(int i=1;i<=n;i++)
    {
        while(q.size()&&q.top()<=i)
        {
            int p=q.top();
            q.pop();
            ans++;
            for(int x:g[p])
            {
                if(vis[x])continue;
                q.push(x);
                vis[x]=1;
            }
        }
        if(ans<i) cout<<"-1\n";
        else cout<<q.size()<<"\n";
    }
    return 0;
}

AC 记录

最后我们的这道题也是成功的 AC 了