题解：CF1693C Keshi in Search of AmShZ

我们倒着思考，考虑一种类似 DP 的方法：设

f_u

表示从点

u

走到目标点的最小代价，则有

f_u=\min\limits_{v \in nxt_u} (f_v+\sum\limits_{v' \in nxt_u}[f_{v'} > f_v] + 1)

。

这个式子比较好理解：我们考虑我们最后一定会选一条边走出这个点，钦定当前选定的边是

u \to v

，则首先把

f_{v'}>f_v

的边

u \to v'

封住一定是不劣的。然后由于现在要花时间向外走一步，故代价要加上

1

。这样做就出现了一个问题：我们的图是存在环的，无法确定更新的先后顺序以在一次遍历中确定最终

f

的值，而每次暴力遍历所有点和其出边直到不能再更新

f

的值又会导致时间复杂度不可接受。

注意到 DP 值非负，考虑 Dijkstra trick 优化该 DP。我们从终点

n

开始采用类似 Dijkstra 的方式从小到大确定

f

的值，这样我们就能在

O(m \log m)

的时间复杂度内求解完所有的 DP 值。同时这样做我们

\sum

内的值也是容易计算的。

代码：

CPP

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define pii pair <int , int>
#define pb push_back
#define fi first
#define se second
#define fastio ios::sync_with_stdio(false) , cin.tie(0) , cout.tie(0);
using namespace std;
const int MAXN = 2e5 + 10 , INF = 0x3f3f3f3f;
int n , m;
int f[MAXN] , cnt[MAXN];
bitset <MAXN> vis;
struct node
{
	int id;
	int val;
	bool operator < (const node &x) const {return val > x.val;}
};
vector <int> a[MAXN];
priority_queue <node> q;
void solve()
{
	q.push({n , 0});
	while(!q.empty())
	{
		auto now = q.top();
		q.pop();
		if(vis[now.id]) continue;
		vis[now.id] = 1;
		f[now.id] = now.val;
		for(int i : a[now.id])
		{
			if(vis[i]) continue;
			q.push({i , now.val + cnt[i]});
			cnt[i]--;
		}
	}
	return;
}
int main()
{
	fastio;
	cin >> n >> m;
	for(int i = 1 ; i <= m ; i++)
	{
		int u , v;
		cin >> u >> v;
		a[v].pb(u);
		cnt[u]++;
	}
	memset(f , INF , sizeof(f));
	solve();
	cout << f[1];
	return 0;
}

题解：CF1693C Keshi in Search of AmShZ

文章操作

相关推荐

评论

题解：CF1693C Keshi in Search of AmShZ