1, Content

If the state transition equation of \ (DP \) is \ (f[i]=min\{f[i],\sum f[j]+k \} \)

Then we can consider optimizing it with the idea of \ (Dij \)

Because if the \ (f \) value of a point is the smallest, no other point can affect it

Therefore, every time we take the smallest point from the heap and update other points

2, Examples

1. Luogu P4745 [CERC2017]Gambling Guide

Title Description

Portal

analysis

According to the general practice of expectation questions, we set \ (f[u] \) as the expected cost from \ (U \) to the end \ (n \)

Set \ (du[u] \) as the outgoing degree of node \ (U \)

Then \ (f [u] = \ frac {\ sum {U - > V} min (f [u], f [v])} {Du [u]} + 1 \)

We will find that this formula contains both \ (f[u] \) itself and the point \ (f[v] \) adjacent to \ (f[u] \)

Bad direct transfer

But we can be sure that if \ (f[v] < f[u] \), then \ (f[v] \) will certainly contribute to \ (f[u] \)

Therefore, we can use the idea of \ (Dij \) to open a small root heap and take out the smallest one each time to update others

Because the current value is the smallest, there must be no other point that can affect it

We set \ (u \) to be updated \ (cnt \) times by the \ (f \) value of the point adjacent to it, and the sum of these values is \ (sum \)

Then \ (f[u]=\frac{sum+(du[u]-cnt[u]) \times f[u]}{du[u]}+1 \)

Available \ (f[u]=\frac{sum+du[u]}{cnt} \)

code

#include<cstdio>
#include<cstring>
#include<queue>
const int maxn=6e5+5;
inline int read(){
	int x=0,fh=1;
	char ch=getchar();
	while(ch<'0' || ch>'9'){
		if(ch=='-') fh=-1;
		ch=getchar();
	}
	while(ch>='0' && ch<='9'){
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	return x*fh;
}
int head[maxn],tot=1;
struct asd{
	int to,next;
}b[maxn];
void ad(int aa,int bb){
	b[tot].to=bb;
	b[tot].next=head[aa];
	head[aa]=tot++;
}
struct jie{
	int num;
	double jl;
	jie(){}
	jie(int aa,double bb){
		num=aa,jl=bb;
	}
	bool operator < (const jie &A) const{
		return jl>A.jl;
	}
};
int n,m,du[maxn],cnt[maxn];
double sum[maxn],f[maxn];
bool vis[maxn];
std::priority_queue<jie> q;
void dij(){
	q.push(jie(n,0));
	while(!q.empty()){
		int now=q.top().num;
		q.pop();
		if(vis[now]) continue;
		vis[now]=1;
		for(int i=head[now];i!=-1;i=b[i].next){
			int u=b[i].to;
			if(vis[u]) continue;
			cnt[u]++;
			sum[u]+=f[now];
			f[u]=(du[u]+sum[u])/cnt[u];
			q.push(jie(u,f[u]));
		}
	}
}
int main(){
	memset(head,-1,sizeof(head));
	n=read(),m=read();
	for(int i=1;i<=m;i++){
		int aa,bb;
		aa=read(),bb=read();
		ad(aa,bb);
		ad(bb,aa);
		du[aa]++,du[bb]++;
	}
	dij();
	printf("%.10f\n",f[1]);
	return 0;
}

2. Li Qing (internal question)

Title Description

Portal

analysis

We set the cost of eliminating the head of (I) as \ (f[i] \)

Then \ (f [i] = min (f [i], a [i] + \ sum, f [J], B [i]) \)

Similarly, we throw all the \ (f \) values into the small root heap at the beginning

Update the first value of other elements every time

code

#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
#include<iostream>
#include<cstdlib>
const int maxn=6e5+5;
typedef long long ll;
int head[maxn],tot=1;
struct asd{
	int to,next;
}b[maxn];
int n;
void ad(int aa,int bb){
	b[tot].to=bb;
	b[tot].next=head[aa];
	head[aa]=tot++;
}
struct jie{
	int num;
	ll jl;
	jie(){}
	jie(int aa,ll bb){
		num=aa,jl=bb;
	}
	bool operator < (const jie &A) const{
		return jl>A.jl;
	}
};
ll a[maxn],f[maxn];
int k[maxn];
bool vis[maxn];
std::priority_queue<jie> q;
void dij(){
	while(!q.empty()){
		int now=q.top().num;
		q.pop();
		if(vis[now]) continue;
		vis[now]=1;
		if(k[now]==0) f[now]=std::min(f[now],a[now]);
		for(int i=head[now];i!=-1;i=b[i].next){
			int u=b[i].to;
			if(!vis[u]){
				a[u]+=f[now];
				k[u]--;
				if(k[u]==0) q.push(jie(u,a[u]));
			}
		}
	}
}
int main(){
	memset(head,-1,sizeof(head));
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%lld%lld%d",&a[i],&f[i],&k[i]);
		q.push(jie(i,f[i]));
		for(int j=1;j<=k[i];j++){
			int aa;
			scanf("%d",&aa);
			ad(aa,i);
		}
	}
	dij();
	long long ans=0;
	for(int i=1;i<=n;i++){
		ans+=f[i];
	}
	printf("%lld\n",ans);
	return 0;
}