【SDOI 2010】魔法猪学院

【SDOI 2010】魔法猪学院

【题目】

传送门

题目描述：

iPig 在假期来到了传说中的魔法猪学院，开始为期两个月的魔法猪训练。经过了一周理论知识和一周基本魔法的学习之后，iPig 对猪世界的世界本原有了很多的了解：众所周知，世界是由元素构成的；元素与元素之间可以互相转换；能量守恒……。

能量守恒……iPig 今天就在进行一个麻烦的测验。iPig 在之前的学习中已经知道了很多种元素，并学会了可以转化这些元素的魔法，每种魔法需要消耗 iPig 一定的能量。作为 PKU 的顶尖学猪，让 iPig 用最少的能量完成从一种元素转换到另一种元素……等等，iPig 的魔法导猪可没这么笨！这一次，他给 iPig 带来了很多 1 1 1 号元素的样本，要求 iPig 使用学习过的魔法将它们一个个转化为 n n n 号元素，为了增加难度，要求每份样本的转换过程都不相同。这个看似困难的任务实际上对 iPig 并没有挑战性，因为，他有坚实的后盾……现在的你呀！

注意，两个元素之间的转化可能有多种魔法，转化是单向的。转化的过程中，可以转化到一个元素（包括开始元素）多次，但是一但转化到目标元素，则一份样本的转化过程结束。iPig 的总能量是有限的，所以最多能够转换的样本数一定是一个有限数。具体请参看样例。

输入格式：

第一行三个数 n n n、 m m m、 E E E 表示 iPig 知道的元素个数（元素从 1 1 1 到 n n n 编号）、iPig 已经学会的魔法个数和 iPig 的总能量。

后跟 m m m 行每行三个数 s i s_i si​、 t i t_i ti​、 e i e_i ei​ 表示 iPig 知道一种魔法，消耗 e i e_i ei​ 的能量将元素 s i s_i si​ 变换到元素 t i t_i ti​

输出格式：

一行一个数，表示最多可以完成的方式数。输入数据保证至少可以完成一种方式。

样例数据：

输入
4 6 14.9
1 2 1.5
2 1 1.5
1 3 3
2 3 1.5
3 4 1.5
1 4 1.5

输出
3

提示：

【样例解释】
有意义的转换方式共4种：

1->4，消耗能量 1.5
1->2->1->4，消耗能量 4.5
1->3->4，消耗能量 4.5
1->2->3->4，消耗能量 4.5

显然最多只能完成其中的 3 3 3 种转换方式（选第一种方式，后三种方式仍选两个），即最多可以转换 3 3 3 份样本。

如果将 E = 14.9 E=14.9 E=14.9 改为 E = 15 E=15 E=15，则可以完成以上全部方式，答案变为 4 4 4。

【数据规模】

占总分不小于 10 % 10% 10% 的数据满足 n n n ≤ 6 6 6， m m m ≤ 15 15 15。
占总分不小于 20 % 20% 20% 的数据满足 n n n ≤ 100 100 100， m m m ≤ 300 300 300， E E E ≤ 100 100 100 且 E E E 和所有的 e i e_i ei​ 均为整数（可以直接作为整型数字读入）。
所有数据满足 2 2 2 ≤ n n n ≤ 5000 5000 5000， 1 1 1 ≤ m m m ≤ 200000 200000 200000， 1 1 1 ≤ E E E ≤ 1 0 7 10^7 107， 1 1 1 ≤ e i e_i ei​ ≤ E E E， E E E 和所有的 e i e_i ei​ 为实数。

【分析】

题解：A*算法

第一次接触 A* 算法，觉得这个算法比较玄妙，和爆搜不一样的是，它像是一种贪心版的 d f s dfs dfs

启发函数 f ( i ) = g ( i ) + h ( i ) f(i)=g(i) + h(i) f(i)=g(i)+h(i) 表示估计的该结点的好坏（一般越小代表这个点越优），其中 g ( i ) g(i) g(i) 表示从初始结点到 i i i 的路径长度， h ( i ) h(i) h(i) 表示从 i i i 到目标结点的距离的估计（估计值不能大于实际代价）。A* 算法每次选择 f ( i ) f(i) f(i) 最小的点进行拓展

我们把 h ( i ) h(i) h(i) 叫做估价函数，我觉得它是 A* 算法的核心，只要 h ( i ) h(i) h(i) 足够优秀，搜索就会很快

怎么确定估计值呢，比如说对于这道题，可以简单地看成 t t t 到各个点的最短路（这样 h ( i ) h(i) h(i) 肯定是比实际要小的）

这里摘一个证明
证明： 当 h ( i ) h(i) h(i) 小于等于真实距离时是真实解，因为通过 f ( i ) f(i) f(i) 的比较每次被临时放弃的节点都是因为自己的 f ( i ) f(i) f(i) 比别人的大，而自己的 g ( i ) g(i) g(i) 是真实距离， h ( i ) h(i) h(i) 又小于等于真实距离，所以这个被放弃的点在这一步的确不是最优解，直到它可能是最优解的时候它才会被搜索。 故得证。

A* 算法我觉得先感性理解就行了，先不要过多地深究，不然可能会把自己绕晕

P s Ps Ps：洛谷上这道题貌似卡 A* 算法，可以去其他的网站去交

【代码】

#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 5005
#define M 200005
using namespace std;
int n,m,t1,t2,ans;double e,dist[N];
int first[N],v[M],nxt[M];double w[M];
int First[N],V[M],Nxt[M];double W[M];
struct node{int x;double cost;};
bool operator<(const node &p,const node &q)  {return dist[p.x]&#st>dist[q.x]&#st;}
void add(int x,int y,double z)  {nxt[++t1]=first[x];first[x]=t1;v[t1]=y;w[t1]=z;}
void readd(int x,int y,double z)  {Nxt[++t2]=First[x];First[x]=t2;V[t2]=y;W[t2]=z;}
priority_queue<pair<double,int> >q;
void dijkstra(int s)
{int x,y,i;memset(dist,127,sizeof(dist));q.push(make_pair(0,s));dist[s]=0;while(!q.empty()){x&#p().second;q.pop();for(i=First[x];i;i=Nxt[i]){y=V[i];if(dist[y]>dist[x]+W[i]){dist[y]=dist[x]+W[i];q.push(make_pair(-dist[y],y));}}}
}
priority_queue<node>que;
void A_star()
{que.push((node){1,0});while(!pty()){node now&#p();que.pop();if(now.x==n){e-&#st;if(e<0)  return;ans++;continue;}int i,j;for(i=first[now.x];i;i=nxt[i]){j=v[i];que.push((node){st+w[i]});}}
}
int main()
{int x,y,i;double z;scanf("%d%d%lf",&n,&m,&e);for(i=1;i<=m;++i){scanf("%d%d%lf",&x,&y,&z);add(x,y,z),readd(y,x,z);}dijkstra(n);A_star();printf("%d",ans);return 0;
}