五月份没有写过blog.
期中考刚过......漫漫文化课,无尽头.
马上要为联赛开坑了,激动啊.
刚听了孙柘的演讲..%%%
最近刷的题只有一道启发式合并,一道分层图,一道差分约束..然后不知不觉破80啦
80其实是个很小的题量,但是之所以想讲一下是因为
自己在70+的位置浪了很久吧,所以衍生出一种好难破80的feel~
打算去看A*算法和K短路,
poj1077--Eight(据shy说A*入门题)
被自己逗笑了..居然开始写暴力了..因为这里暴力不虚..再加上个人看到A*淦不动啊 于是码了一道裸的bfs果然没什么营养..说好的要写A*呢!
里面敲了个康托展开,哈希利器啊
ll fold()
{
ll temp,t=;
;i<;i++)
{
temp=;
;j<;j++)
if(a1.num[j]<a1.num[i])temp++;
t+=temp*jc[-i];
} return t;
}
然后听说bzoj1073是道K短路,又是一道二百人AC的首页题..可怕..还有十分要cheat..不是很想做啊..但是这道题有份题解很兹辞
传送门:http://z55250825.blog.163.com/blog/static/150230809201422581743407/
然后必刷水题poj2449,在这里MARK一下.
poj2449
第一次写stl的优先队列,果然方便啊..这里有两个没弄懂的点:
1.A结构的定义 const const是什么鬼
2.原blog http://blog.csdn.net/sdj222555/article/details/7690081,明明都考虑了有环的情况呀,这样spfa()不是会爆炸?在comments评论了,博主还未解答.//已解决,我sb了
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#define N 500005
#define inf 1000000000
using namespace std;
int edgenum,x,y,k,w,n,m,st,ed;
],pri[N];
struct A
{
int f,g,v;
bool operator <(const A a)const
{
if(a.f==f)return a.f<g;
return a.f<f;
}
};
void add(int u,int v,int w)
{
edgenum++;vet[edgenum]=v;next[edgenum]=head[u];head[u]=edgenum;pri[edgenum]=w;
edgenum++;vet[edgenum]=u;next[edgenum]=head[v];head[v]=edgenum;pri[edgenum]=w;
}
void spfa(int src)
{
;i<=n;i++)dis[i]=inf;dis[src]=;
memset(flag,,,tail=;q[]=src;
while(tou<=tail)
{
;
)
{
int v=vet[e];
==){e=next[e];continue;}
if(dis[v]>dis[u]+pri[e])
{
dis[v]=dis[u]+pri[e];
)
{
tail++;q[tail]=v;flag[v]=;
}
}
e=next[e];
}
tou++;
}
}
int Astar(int st,int ed)
{
;priority_queue<A>Q;
if(st==ed)k++;
;
A t,tt;
t.v=st;t.g=;t.f=t.g+dis[st];Q.push(t);
while(!Q.empty())
{
tt=Q.top();Q.pop();//把tt弹出队列
if(tt.v==ed)
{
cnt++;if(cnt==k)return tt.g;
}
int u=tt.v,e=head[u];
)
{
==){e=next[e];continue;}
t.v=vet[e];
t.g=tt.g+pri[e];t.f=t.g+dis[t.v];Q.push(t);//F(v)=f(v)+h(v);
e=next[e];
}
}
;
}
int main()
{
scanf("%d%d",&n,&m);
;i<=m;i++)
{
scanf("%d%d%d",&x,&y,&w);
add(x,y,w);
}
scanf("%d%d%d",&st,&ed,&k);
spfa(ed);
printf("%d\n",Astar(st,ed));
;
}
刷了一道bzoj1957,感觉这题真高明啊,手写堆党拽起啊,hhh
debug的时候又发现自己各种sb打错,粗心活该
#include<cstdio>
#include<algorithm>
#include<cstring>
#define ll long long
#define inf 2000000000000
#define N 400005
using namespace std;
struct A
{
double f,g;
int v;
};
A a[];
],top,vet[N],next[N],head[N],q[N];
double e,pri[N],dis[N];
bool comp(A a,A b)
{
;;
return(a.g<b.g);
}
void push_up(int kk)
{
int k=kk;
>&&comp(a[k],a[k/]))
{
A t;t=a[k];a[k]=a[k/];a[k/]=t;
//swap(a[k],a[k/2]);
k=k/;
}
}
void push_down(int kk)
{
int k=kk;
<=top)
{
+<=top&&comp(a[k*+],a[k])&&comp(a[k*+],a[k*]))
{
A t;t=a[k];a[k]=a[k*+];a[k*+]=t;
//swap(a[k],a[k*2+1]);
k=k*+;
}],a[k]))
{
A t;t=a[k];a[k]=a[k*];a[k*]=t;
//swap(a[k],a[k*2]);
k=k*;
}else break;
}
}
void add(int u,int v,double w)
{
edgenum++;vet[edgenum]=v;next[edgenum]=head[u];head[u]=edgenum;pri[edgenum]=w;
}
void spfa(int src)
{
memset(flag,,sizeof(flag));
;i<=n;i++)dis[i]=inf;flag[src]=;dis[src]=;q[]=src;
,tail=;
while(tou<=tail)
{
int u=q[tou%N],ee=head[u];
)
{
int v=vet[ee];
==){ee=next[ee];continue;}
if(dis[v]>dis[u]+pri[ee])
{
dis[v]=dis[u]+pri[ee];
)tail++,q[tail%N]=v,flag[v]=;
}
ee=next[ee];
}
tou++;flag[u]=;
}
}
int Astar(int st ,int ed)
{
;
A t,tt;;
t.v=st;t.g=;t.f=dis[st];a[]=t;top=;
)
{
tt=a[];a[]=a[top];top--;push_down();
//for(int i=1;i<=top;i++)printf("%lf ",a[i].f);printf("\n");
if(tt.v==ed)
{
//printf("%lf %lf\n",tt.f,e);
if(e>=tt.g)e-=tt.g,cnt++;else return cnt;
}
int u=tt.v,ee=head[u];
)
{
==){ee=next[ee];continue;}
t.v=vet[ee];t.g=tt.g+pri[ee];t.f=t.g+dis[t.v];top++;a[top]=t;push_up(top);
ee=next[ee];
}
}
return cnt;
}
int main()
{
scanf("%d%d%lf",&n,&m,&e);int u,v;double w;
;i<=m;i++)
{
scanf("%d%d%lf",&u,&v,&w);
add(u,v,w);add(v,u,w);
}
spfa(n);printf(,n));
}
还有,还没动过计算几何怎么办啊%>_<%