题解 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 算法的实现。 ```cpp #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 以及感觉这场后面几个题也都不错。~~虽然好像很码，呜呜呜。~~