?

題目描述

iPig在假期來到了傳說中的魔法豬學院，開始為期兩個月的魔法豬訓練。經(jīng)過了一周理論知識和一周基本魔法的學習之后，iPig對豬世界的世界本原有了很多的了解：眾所周知，世界是由元素構(gòu)成的；元素與元素之間可以互相轉(zhuǎn)換；能量守恒……。

能量守恒……iPig 今天就在進行一個麻煩的測驗。iPig 在之前的學習中已經(jīng)知道了很多種元素，并學會了可以轉(zhuǎn)化這些元素的魔法，每種魔法需要消耗 iPig 一定的能量。作為 PKU 的頂尖學豬，讓 iPig 用最少的能量完成從一種元素轉(zhuǎn)換到另一種元素……等等，iPig 的魔法導豬可沒這么笨！這一次，他給 iPig 帶來了很多 1 號元素的樣本，要求 iPig 使用學習過的魔法將它們一個個轉(zhuǎn)化為 N 號元素，為了增加難度，要求每份樣本的轉(zhuǎn)換過程都不相同。這個看似困難的任務實際上對 iPig 并沒有挑戰(zhàn)性，因為，他有堅實的后盾……現(xiàn)在的你呀！

注意，兩個元素之間的轉(zhuǎn)化可能有多種魔法，轉(zhuǎn)化是單向的。轉(zhuǎn)化的過程中，可以轉(zhuǎn)化到一個元素（包括開始元素）多次，但是一但轉(zhuǎn)化到目標元素，則一份樣本的轉(zhuǎn)化過程結(jié)束。iPig 的總能量是有限的，所以最多能夠轉(zhuǎn)換的樣本數(shù)一定是一個有限數(shù)。具體請參看樣例。

輸入輸出格式

輸入格式：

?

第一行三個數(shù) N、M、E 表示iPig知道的元素個數(shù)（元素從 1 到 N 編號）、iPig已經(jīng)學會的魔法個數(shù)和iPig的總能量。

后跟 M 行每行三個數(shù) si、ti、ei 表示 iPig 知道一種魔法，消耗 ei 的能量將元素 si 變換到元素 ti 。

?

輸出格式：

?

一行一個數(shù)，表示最多可以完成的方式數(shù)。輸入數(shù)據(jù)保證至少可以完成一種方式。

?

輸入輸出樣例

輸入樣例#1：
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 輸出樣例#1：
3

說明

有意義的轉(zhuǎn)換方式共4種：

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

顯然最多只能完成其中的3種轉(zhuǎn)換方式（選第一種方式，后三種方式仍選兩個），即最多可以轉(zhuǎn)換3份樣本。 如果將 E=14.9 改為 E=15，則可以完成以上全部方式，答案變?yōu)?4。

數(shù)據(jù)規(guī)模

占總分不小于 10% 的數(shù)據(jù)滿足 N <= 6，M<=15。

占總分不小于 20% 的數(shù)據(jù)滿足 N <= 100，M<=300，E<=100且E和所有的ei均為整數(shù)（可以直接作為整型數(shù)字讀入）。

所有數(shù)據(jù)滿足 2 <= N <= 5000，1 <= M <= 200000，1<=E<=107，1<=ei<=E，E和所有的ei為實數(shù)。

?

A星算法。先從終點SPFA到起點估價，然后A星寬搜（用堆維護花費最少的方案），每到終點就累加方案。

然而這題神TM卡priority_queue，用stl會MLE，非要手寫堆才能過。

（根據(jù)dalao所說，這題省選原題限制內(nèi)存256M，放到OJ上限制就改成了64M）

但是灑家不想向手寫勢力低頭！

各種花式卡時，刷了一頁評測記錄，終于從50卡到80，從80卡到90，從90卡到AC。

在！這！停！頓！時間總計1小時45分鐘

感到肝力上升了……

?

1 /*by SilverN*/ 2 #include<algorithm> 3 #include<iostream> 4 #include<cstring> 5 #include<cstdio> 6 #include<cmath> 7 #include<queue> 8 using namespace std; 9 const double eps=1e-7; 10 int read(){ 11 int x=0,f=1;char ch=getchar(); 12 while(ch<'0' || ch>'9'){if(ch=='-')f=-1;ch=getchar();} 13 while(ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();} 14 return x*f; 15 } 16 const int mxn=200100; 17 struct edge{ 18 int v,nxt; 19 double dis; 20 }e[mxn],mp[mxn]; 21 int hd1[5002],hd2[5002]; 22 int mct1=0,mct2=0; 23 inline void add_edge(int u,int v,double dis){ 24 e[++mct1].v=v;e[mct1].nxt=hd1[u];e[mct1].dis=dis;hd1[u]=mct1; 25 return; 26 } 27 inline void add_edge2(int u,int v,double dis){ 28 mp[++mct2].v=v;mp[mct2].nxt=hd2[u];mp[mct2].dis=dis;hd2[u]=mct2; 29 return; 30 } 31 int n,m; 32 double E; 33 // 34 35 double dis[5002]; 36 struct target{ 37 unsigned short int u; 38 float w; 39 }; 40 bool operator< (target aa,target an) 41 {return aa.w+dis[aa.u]>an.w+dis[an.u];} 42 priority_queue<target>tp; 43 // 44 bool inq[5002]; 45 int head=0,tl=1; 46 int q[5010]; 47 void SPFA(){ 48 memset(dis,127,sizeof dis); 49 q[++head]=n; 50 dis[n]=0; 51 inq[n]=1; 52 int i,j; 53 while(head!=tl+1){ 54 int u=q[head++];if(head==5010)head=0; 55 for(register int i=hd2[u];i;i=mp[i].nxt){ 56 int v=mp[i].v; 57 if(dis[v]>dis[u]+mp[i].dis){ 58 dis[v]=dis[u]+mp[i].dis; 59 if(!inq[v]){ 60 inq[v]=1; 61 tl++;if(tl==5010)tl=0; 62 q[tl]=v; 63 } 64 } 65 } 66 inq[u]=0; 67 } 68 } 69 int ans=0; 70 void gt(){//A* 71 int i,j; 72 tp.push((target){1,0}); 73 while(!tp.empty()){ 74 target x=tp.top();tp.pop(); 75 if(x.u==n){ 76 E-=x.w; 77 78 // if(smm>E)break; 79 if(E+eps<0)return; 80 ans++; 81 continue; 82 } 83 if(x.w+dis[x.u]>E)continue; 84 for(register int i=hd1[x.u];i;i=e[i].nxt){ 85 tp.push( (target){e[i].v,x.w+e[i].dis} ); 86 } 87 } 88 return; 89 } 90 // 91 int main(){ 92 int i,j; 93 scanf("%d%d%f",&n,&m,&E); 94 int u,v; 95 float d; 96 for(register int i=1;i<=m;i++){ 97 // scanf("%d%d%lf",&u,&v,&d); 98 u=read(); 99 v=read(); 100 scanf("%f",&d); 101 add_edge(u,v,d); 102 add_edge2(v,u,d); 103 } 104 SPFA(); 105 gt(); 106 printf("%d\n",ans); 107 return 0; 108 }

?

轉(zhuǎn)載于:https://www.cnblogs.com/SilverNebula/p/5922479.html

總結(jié)

以上是生活随笔為你收集整理的洛谷P2483 Bzoj1975 [SDOI2010]魔法猪学院的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。