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

时光机TimeMachine

——一个退役OIer

 
 
 

日志

 
 

[BZOJ1975][Sdoi2010]魔法猪学院  

2015-03-17 10:20:45|  分类: Problems |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

1975: [Sdoi2010]魔法猪学院

看过好几次都不太会做……
感谢GTY神犇指导
题解在代码下方

#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<queue>
using namespace std;
int scan(){
char cc=' ';int re=0,fh=1;while(cc==' '||cc=='\r'||cc=='\n')cc=getchar();
if(cc=='+')cc=getchar(),fh=1;if(cc=='-')cc=getchar(),fh=-1;
while('0'<=cc&&cc<='9'){re=re*10+cc-'0';cc=getchar();}return re*fh;
}
const int N = 5000+100;
const int M = 2E5+100;
const double eps = 1e-10;

int n,m,st[N],ans;
int cot[N],K;
double all;

namespace A{
struct Point{
int d;double len;Point *next;
void push(int a,double b){
Point *l = new Point;
l->d = a;l->len = b;l->next = next;
next = l;
}
}point[N];
double dis[N];
short v[N];
queue<int>que;
void spfa(){
for(int i=1;i<=n;i++)dis[i]=1e50;
que.push(n);dis[n] = 0;
while(!que.empty()){
int now = que.front();que.pop();
for(Point *i = point[now].next;i!=NULL;i=i->next)
if(dis[now]+i->len+eps < dis[i->d]){
dis[i->d] = dis[now] + i->len;
if(!v[i->d])
que.push(i->d);
}
}
}
}
struct Node{Node(int aa=0,int bb=0,double cc=0){a=aa;b=bb;c=cc;}short a;int b;double c;}
edges[M];
bool operator < (const Node&a,const Node&b){
return a.c>b.c;
}
priority_queue<Node>dui;
bool ecmp(const Node&a,const Node&b){
if(a.a!=b.a)return a.a<b.a;
return a.c < b.c;
}
void update(int from,double dis){
if(from == n){
cot[n]++;
all -= dis;
K = cot[n] + floor(all/A::dis[1]);
// printf("end!\n");
return;
}
if(cot[from] > K)return;
if(!st[from])return;
if(dis > all+eps)return;
Node now(from,st[from],dis);
now.c -= A::dis[from];
now.c += edges[now.b].c + A::dis[edges[now.b].b];
if(all+eps>=now.c){
cot[now.a]++;
dui.push(now);
}
}
int main(){
// freopen("in.txt", "r", stdin);
int i,j,a,b;double c;
scanf("%d%d%lf",&n,&m,&all);
// printf("%d %d\n",n,m);
for(i=1;i<=m;i++){
a=scan();b=scan();
// printf("%d->%d\n",a,b);
scanf("%lf",&c);
edges[i]=Node(a,b,c);
A::point[b].push(a,c);
}
A::spfa();
K = floor(all/A::dis[1]);
for(i=1;i<=m;i++){
edges[i].c += A::dis[edges[i].b];
}
sort(edges+1,edges+1+m,ecmp);
for(i=1;i<=m;i++){
edges[i].c -= A::dis[edges[i].b];
if(!st[edges[i].a]){
st[edges[i].a]=i;
}
}
for(i=m;i>1;i--)
if(edges[i].a==edges[i-1].a){
edges[i].c-=edges[i-1].c;
}
// for(i=1;i<=n;i++)printf("%d ",st[i]);printf("\n");
if(!st[1]){printf("0\n");return 0;}
dui.push(Node(1,1,edges[1].c+A::dis[edges[1].b]));
i=1;
//for(i=1;i<=n;i++)printf("%.2f ",A::dis[i]);printf("\n");
while(!dui.empty()){
Node now = dui.top();dui.pop();
// printf("%d %d %.1f\n",now.a,edges[now.b].b,now.c);
if(now.c > all+eps)break;
/* if(i == 2 || i == 4){
printf("aa");
}*/
update(edges[now.b].b,now.c);
//push itself
if(edges[now.b+1].a == now.a){
now.c-=A::dis[edges[now.b].b];
now.b++;
now.c+=edges[now.b].c;
now.c+=A::dis[edges[now.b].b];
if(all+eps>=now.c)
dui.push(now);
}i++;
}
printf("%d\n",cot[n]);
return 0;
}



我看的一篇题解:
没找到原文章真是抱歉= =。

A* + 堆暴力(K短路)
首先看到边权  1,所以感觉大概可以用堆暴力……
不过感觉复杂度很不靠谱……但是感觉也并没有什么更好的办法
所以就只好随便写了一下,然后发现只过了5个点……剩下的点>10s
然后我想了一下剪枝……先求出来每个点到n的最短路,如果当前距离+最短路>剩余的能量就剪掉
不过感觉没啥威力……依旧只过5个点,但是有其它两个点<5s
然后不知道怎么搞了……GTY大爷告诉我要把堆的关键字改成当{前距离+该点到n的最短路},这样能不仅保证答案,而且感觉暴力的顺序也更靠谱了……
最后又加了网上文章的剪枝……估计一下k,每个点不能被更新K+1次
然后总时间<1s飞速过掉了QAQ
  评论这张
 
阅读(485)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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