记忆的轮廓
题目描述
通往贤者之塔的路上，有许多的危机。
我们可以把这个地形看做是一颗树，根节点编号为1，目标节点编号为n，其中1-n的简单路径上，编号依次递增，在[1,n]中，一共有n个节点。我们把编号在[1,n]的叫做正确节点，[n+1,m]的叫做错误节点。一个叶子，如果是正确节点则为正确叶子，否则称为错误叶子。莎缇拉要帮助昴到达贤者之塔，因此现在面临着存档位置设定的问题。
为了让昴成长为英雄，因此一共只有p次存档的机会，其中1和n必须存档。被莎缇拉设置为要存档的节点称为存档位置。当然不能让昴陷入死循环，所以存档只能在正确节点上进行，而且同一个节点不能存多次档。因为通往贤者之塔的路上有影响的瘴气，因此莎缇拉假设昴每次位于树上一个节点时，都会等概率选择一个儿子走下去。每当走到一个错误叶子时，再走一步就会读档。具体的，每次昴到达一个新的存档位置，存档点便会更新为这个位置（假如现在的存档点是i，现在走到了一个存档位置j>i，那么存档点便会更新为j）。读档的意思就是回到当前存档点。初始昴位于1，当昴走到正确节点n时，便结束了路程。莎缇拉想知道，最优情况下，昴结束路程的期望步数是多少？
输入格式
第一行一个正整数T表示数据组数。
接下来每组数据，首先读入三个正整数n,m,p。
接下来m-n行，描述树上所有的非正确边（正确边即连接两个正确节点的边）
用两个正整数j，k表示j与k之间有一条连边，j和k可以均为错误节点，也可以一个为正确节点另一个为错误节点。
数据保证j是k的父亲。
50<=p<=n<=700，m<=1500，T<=5。
数据保证每个正确节点均有至少2个儿子，至多3个儿子。
输出格式
T行每行一个实数表示每组数据的答案。请保留四位小数。
样例
样例输入
1
3 7 2
1 4
2 5
3 6
3 7样例输出
9.0000 题解 考场上推出了一个死掉的弱智算法
然而精度出了问题，加上本题根本没有小数据，被强行卡成了0分
我们不关注走到错误节点之后的去向
只要dfs处理出 每个正确节点的错误节点儿子走出树的期望步数即可
设dp（i，j）表示从第n个点，中间存了j个档，第j个存档在节点i的期望步数，
使用高斯消元的思想，我们可以得到dp（i，j）由dp（k，j-1）转移的公式 （i<k≤n）dfs打出来即可
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const double inf=1e10;
const int N=,M=;
int n,m,p,tot;
int first[M],to[M],nxt[M],cd[M];
double w[M],dp[N][N];
void dfs(int x)
{
if(x==n) return ;
if(x<n) dfs(x+);
w[x]=;
for(int i=first[x];i;i=nxt[i])
{
dfs(to[i]);
w[x]+=w[to[i]]/cd[x];
}
}
void add(int a,int b)
{
cd[a]++;
to[++tot]=b;
nxt[tot]=first[a];
first[a]=tot;
}
inline int read()
{
int x=; char ch=getchar();
while(!isdigit(ch)) ch=getchar();
while(isdigit(ch))
{
x=(x<<)+(x<<)+(ch^);
ch=getchar();
}
return x;
}
int th;
pair<double,double> search(int pos,int aim,int k)//系数 常数
{
pair<double,double> now,f;
if(pos>n)
{
now.first=; now.second=w[pos];
return now;
}
if(pos==aim)
{
now.first=; now.second=dp[aim][k]+;
return now;
}
now.first=now.second=;
f=search(pos+,aim,k);
now.first+=f.first/cd[pos];
now.second+=f.second/cd[pos];
for(int i=first[pos];i;i=nxt[i])
{
f=search(to[i],aim,k);
now.first+=f.first/cd[pos];
now.second+=f.second/cd[pos];
}
if(pos!=th) now.second+=;
return now;
}
void dpt(int pos,int k)//在pos处 第k个存档
{
th=pos;
for(int i=pos+;i<=min(n,n-k+);i++)//由在i处 存k-1个档转移
{
pair<double,double> now=search(pos,i,k-);
dp[pos][k]=min(dp[pos][k],now.second/(-now.first));
}
}
int main()
{
int T; T=read();
while(T--)
{
memset(first,,sizeof(first));
memset(cd,,sizeof(cd));
tot=;
n=read(); m=read(); p=read();
for(int i=;i<=n;i++)
for(int j=;j<=n;j++)
dp[i][j]=inf;
for(int i=,f,t;i<=m-n;i++)
{
f=read(); t=read();
add(f,t);
}
dfs();
for(int i=;i<=m;i++) w[i]+=;
for(int i=;i<=n;i++) cd[i]++;
dp[n][]=;
for(int i=n-;i>=;i--)
for(int j=;j<=min(p,n-i+);j++)
dpt(i,j);
printf("%.4lf",dp[][p]);
}
return ;
}
/*
1
3 7 2
1 4
2 5
3 6
3 7
*/
将重复的dfs删去，改成循环的形式，可以得到O（np）的算法
然而被卡了精度，只好改了longdouble
正解（或许）
四边形不等式：对于任意a<b<=c<d，
转移代价w满足w(a,d)+w(b,c)<=w(a,c)+w(b,d)
对于形如 f[i]=max{f[i],f[j]+w(j,i)} 的转移方程
满足决策单调性，即如果i的最优决策点在j，大于i的任何元素的最优决策点一定大于等于j
预处理出从存档点i到存档点j的cost数组
结合实际意义发现满足四边形不等式
于是可以用决策单调性
使「1，n」区间决策「1，n」区间
在向下递归过程中，扫一遍决策区间，找出 被决策区间中点 的最优决策点
中点左侧的区间，由最优决策点及左侧的区间决策
右侧的区间由右侧的区间决策
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=,M=;
const double inf=1e99;
int n,m,p,tot,first[M],to[M],nxt[M],cd[M];
double w[M],dp[N][N],cost[N][N];
void dfs(int x)
{
if(x==n) return ;
if(x<n) dfs(x+);
w[x]=;
for(int i=first[x];i;i=nxt[i])
{
dfs(to[i]);
w[x]+=w[to[i]]/cd[x];
}
}
void add(int a,int b)
{
cd[a]++;
to[++tot]=b;
nxt[tot]=first[a];
first[a]=tot;
}
inline int read()
{
int x=; char ch=getchar();
while(!isdigit(ch)) ch=getchar();
while(isdigit(ch))
{
x=(x<<)+(x<<)+(ch^);
ch=getchar();
}
return x;
}
void solve(int dep,int l,int r,int lf,int rf)//lf rf决策l到r
{
if(l>r) return ;
int mid=l+r>>,home=lf;
dp[mid][dep]=inf;
for(int i=lf;i<=min(rf,mid-);i++)
{
double tmp=dp[i][dep-]+cost[i][mid];
if(tmp<dp[mid][dep]) dp[mid][dep]=tmp,home=i;
}
solve(dep,l,mid-,lf,home);
solve(dep,mid+,r,home,rf);
}
int main()
{
int T; T=read();
while(T--)
{
memset(first,,sizeof(first));
memset(cd,,sizeof(cd));
tot=;
n=read(); m=read(); p=read();
for(int i=,f,t;i<=m-n;i++)
{
f=read(); t=read();
add(f,t);
}
dfs();
for(int i=;i<=m;i++) w[i]+=;
for(int i=;i<=n;i++) cd[i]++;
for(int i=;i<=n;i++)
{
cost[i][i]=;
for(int j=i+;j<=n;j++)
{
cost[i][j]=cd[j-]*cost[i][j-]+;
for(int u=first[j-];u;u=nxt[u])
cost[i][j]+=w[to[u]];
}
}
for(int i=;i<=n;i++) dp[i][]=inf;
dp[][]=;
for(int i=;i<=p;i++)
solve(i,,n,,n);
printf("%.4lf\n",dp[n][p]);
}
return ;
}
刚开始做的时候inf设的不够大，导致无法更新，也就无法固定决策的区间，出现了问题