注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

n+e

NewWeb:http://trinkle.is-programmer.com/

 
 
 

日志

 
 

[BZOJ1975][Sdoi2010]魔法猪学院  

2015-06-20 16:30:21|  分类: BZOJ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

1975: [Sdoi2010]魔法猪学院

Time Limit: 10 Sec  Memory Limit: 64 MB
Submit: 1092  Solved: 353
[Submit][Status][Discuss]

Description

iPig在假期来到了传说中的魔法猪学院,开始为期两个月的魔法猪训练。经过了一周理论知识和一周基本魔法的学习之后,iPig对猪世界的世界本原有了很多的了解:众所周知,世界是由元素构成的;元素与元素之间可以互相转换;能量守恒……。 能量守恒……iPig 今天就在进行一个麻烦的测验。iPig 在之前的学习中已经知道了很多种元素,并学会了可以转化这些元素的魔法,每种魔法需要消耗 iPig 一定的能量。作为 PKU 的顶尖学猪,让 iPig 用最少的能量完成从一种元素转换到另一种元素……等等,iPig 的魔法导猪可没这么笨!这一次,他给 iPig 带来了很多 1 号元素的样本,要求 iPig 使用学习过的魔法将它们一个个转化为 N 号元素,为了增加难度,要求每份样本的转换过程都不相同。这个看似困难的任务实际上对 iPig 并没有挑战性,因为,他有坚实的后盾……现在的你呀! 注意,两个元素之间的转化可能有多种魔法,转化是单向的。转化的过程中,可以转化到一个元素(包括开始元素)多次,但是一但转化到目标元素,则一份样本的转化过程结束。iPig 的总能量是有限的,所以最多能够转换的样本数一定是一个有限数。具体请参看样例。

Input

第一行三个数 N、M、E 表示iPig知道的元素个数(元素从 1 到 N 编号)、iPig已经学会的魔法个数和iPig的总能量。 后跟 M 行每行三个数 si、ti、ei 表示 iPig 知道一种魔法,消耗 ei 的能量将元素 si 变换到元素 ti 。

Output

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

Sample Input

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

Sample Output

3

HINT

样例解释
有意义的转换方式共4种:
1->4,消耗能量 1.5
1->2->1->4,消耗能量 4.5
1->3->4,消耗能量 4.5
1->2->3->4,消耗能量 4.5
显然最多只能完成其中的3种转换方式(选第一种方式,后三种方式仍选两个),即最多可以转换3份样本。
如果将 E=14.9 改为 E=15,则可以完成以上全部方式,答案变为 4。

数据规模
占总分不小于 10% 的数据满足 N <= 6,M<=15。
占总分不小于 20% 的数据满足 N <= 100,M<=300,E<=100且E和所有的ei均为整数(可以直接作为整型数字读入)。
所有数据满足 2 <= N <= 5000,1 <= M <= 200000,1<=E<=107,1<=ei<=E,E和所有的ei为实数。

Source

Solution

求k短路。2014年ydl论文。
为什么要A*呢?直接用可持久化堆+优先队列就好了。

Code

/**************************************************************
    Problem: 1975
    User: wjy1998
    Language: C++
    Result: Accepted
    Time:336 ms
    Memory:14112 kb
****************************************************************/
 
#include<cstdio>
#include<queue>
#include<algorithm>
typedef float ld;
char ch,B[1<<15],*S=B,*T=B;
#define getc() (S==T&&(T=(S=B)+fread(B,1,1<<15,stdin),S==T)?0:*S++)
#define isd(c) (c>='0'&&c<='9')
int aa;int F(){
    while(ch=getc(),!isd(ch));aa=ch-'0';
    while(ch=getc(),isd(ch))aa=aa*10+ch-'0';return aa;
}
ld dd,ee;ld Fl(){
    while(ch=getc(),!isd(ch));dd=ch-'0';
    while(ch=getc(),isd(ch))dd=dd*10+ch-'0';ee=1;
    if(ch=='.')while(ch=getc(),isd(ch))dd+=(ch-'0')*(ee*=0.1);return dd;
}
#define swap(a,b) (swp=a,a=b,b=swp)
#define N 5010
int n,m,x,y,i,ans,pre[N],et=1,la[N],q[1<<16],l,r,in[N],swp,ht,root[N],arr[500],tar;ld v,d[N],now;double tot;
struct E{int to;ld v;int nxt,flag;}e[400010];
#define add(x,y,v) e[++et]=(E){y,v,la[x]},la[x]=et
void MakeGraph(){
    for(i=1;i<n;i++)d[i]=1e30;
    for(q[l=r=1]=n,in[n]=1;l<=r;in[q[l++]]=0)
    for(i=la[q[l]];i;i=e[i].nxt)if(i&1)
    if(d[e[i].to]>d[q[l]]+e[i].v){
        d[e[i].to]=d[q[l]]+e[i].v,pre[e[i].to]=i;
        if(!in[e[i].to])in[q[++r]=e[i].to]=1;
    }
}
struct H{int ls,rs,d,to;ld v;}t[1<<18];
int merge(int x,int y){
    if(!x||!y)return x+y;
    if(t[x].v>t[y].v)swap(x,y);
    int now=++ht;t[now]=t[x],t[now].rs=merge(t[now].rs,y);
    if(t[t[now].ls].d<t[t[now].rs].d)swap(t[now].ls,t[now].rs);
    return t[now].d=t[t[now].rs].d+1,now;
}
struct P{
    int pos;ld v;
    bool operator<(const P&a)const{return v>a.v;}
}tmp;
std::priority_queue<P>que;
void insP(const P&a){
    if(a.v>tot)return;
    que.push(a);
}
bool cmp(int a,int b){return t[a].v<t[b].v;}
int main(){
    n=F(),ht=m=F(),tot=Fl();
    for(i=1;i<=m;i++)x=F(),y=F(),v=Fl(),add(x,y,v),add(y,x,v);
    MakeGraph();now=d[1];if(now>tot)return puts("0"),0;tot-=now,ans++;
    for(q[l=r=1]=n;l<=r;l++)
    for(i=la[q[l]];i;i=e[i].nxt)if(i&1)
    if(pre[e[i].to]==i)e[i].flag=e[i^1].flag=1,q[++r]=e[i].to;
    for(l=1;l<=r;l++){
        for(tar=0,i=la[x=q[l]];i;i=e[i].nxt)if(~i&1)
        if(e[i].flag==0)t[arr[++tar]=i>>1]=(H){0,0,1,e[i].to,e[i].v-d[x]+d[e[i].to]};
        else root[x]=merge(root[x],root[e[i].to]);
        for(std::sort(arr+1,arr+1+tar,cmp),i=1;i<<1<=tar;i++){
            if((i<<1)<=tar)t[arr[i]].ls=arr[i<<1];
            if((i<<1|1)<=tar)t[arr[i]].rs=arr[i<<1|1];
        }
        root[x]=merge(root[x],arr[1]);
    }
    que.push((P){root[1],t[root[1]].v});
    while(!que.empty()){
        tmp=que.top(),que.pop();
        if(tmp.v+now>tot)break;
        ans++,tot-=tmp.v+now;x=tmp.pos;
        if(t[x].ls)insP((P){t[x].ls,t[t[x].ls].v-t[x].v+tmp.v});
        if(t[x].rs)insP((P){t[x].rs,t[t[x].rs].v-t[x].v+tmp.v});
        insP((P){root[t[x].to],t[root[t[x].to]].v+tmp.v});
    }
    printf("%d\n",ans);
}
  评论这张
 
阅读(220)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018