题解 CF1693C【Keshi in Search of AmShZ】

· · 题解

显然 AmShz 可以先把该封的道路都封了，再指挥 Keshi 行动。剩下的图中，1 不能走到任何一个环。总代价为封的道路数量 + 剩下的图中 1 至 n 的最长路。

直接做也许有些困难。我们先人为添加一条性质：保证原图是有向无环图。可以发现，似乎没有什么直接的贪心做法。考虑 DP。我们设 d_i 表示从 i 到 n 的最小代价。假设我们知道了 i 的所有后继的 d 值 d_1,...,d_k，将它们降序排序。那么封路一定是封 d 值较大的若干条道路。枚举封多少条路，可以得到 d_i=\min_{1\leq x \leq k}\{d_{x}+x\}。在反图上按拓扑序 DP 即可。

回到原题。可能有环怎么办呢？我们可以考虑借用 Dijsktra 算法的思想。初始时，我们令 d_n=0，其余点的 d 值都为正无穷。对于每个还没有确定 d 值的点 u，我们定义它的当前值 c_u 为：假设 u 的所有出边中，还没确定 d 值的点的 d 值都为正无穷，d_u 的值。可以发现，所有 c_u 中最小的那个一定等于最后的 d_u。我们用一个小根堆维护所有的 c，每次取出 c 最小的那个，将它的 d 值确定下来，然后扫描所有指向它的点，更新这些点的 c 值。可以发现，这样每次从堆里取出来的 c 一定是递增的，那么每次用新确定的 d 去更新 c 的时候，实际上只有包含了所有已确定点的方案是需要额外考虑的，因而单次更新可以做到 O(1)。总时间复杂度 O(m\log n)。实现可以类比 Dijsktra 算法的实现。

#include<cstdio>
#include<algorithm>
#include<queue>
#include<vector>

using namespace std;

const int INF=1e9;

typedef pair<int,int> PAIR;

priority_queue<PAIR> pq;
int out[300000];vector<int> ed[300000];bool vis[300000];
int dis[300000];

int main()
{
    int n=0,m=0;scanf("%d%d",&n,&m);
    for(int i=1,x=0,y=0;i<=m;i++)
    {
        scanf("%d%d",&x,&y);out[x]++;ed[y].push_back(x);
    }
    for(int i=1;i<n;i++)dis[i]=INF;
    pq.push(make_pair(0,n));
    while(!pq.empty())
    {
        int u=pq.top().second;pq.pop();
        if(vis[u])continue;vis[u]=1;
        for(int i=0;i<ed[u].size();i++)
        {
            int v=ed[u][i];
            out[v]--;int x=dis[u]+out[v]+1;
            if(dis[v]>x){dis[v]=x;pq.push(make_pair(-dis[v],v));}
        }
    }
    printf("%d",dis[1]);
}

后记

非常喜欢这题。也许这种改造熟知算法的题比较符合我的审美？QaQ

以及感觉这场后面几个题也都不错。虽然好像很码，呜呜呜。