锐客网

  1. 首页 > it技术 > >

#|LOJ#3156. 「NOI2019」回家路线（前缀和优化建图+for循环+凸包）

#前缀和最短路凸包

传送门
来一发大常数做法（然而网络赛的时候凸包插点的方向写反了。。。 40 p t s 40pts 40pts滚了什么我居然还有40）
对于一条边 ( u , v , p , q ) (u,v,p,q) (u,v,p,q)，我们把二元组 ( v , q ) (v,q) (v,q)看成一个点。
这样下来一共有 m m m个点。
假设每个点对应有 l e n 1 i len1_i len1i?个二元组 ( i , v a l 1 i , j ) (i,val1_{i,j}) (i,val1i,j?)，每个时间点对应有 l e n 2 i len2_i len2i?个二元组 ( v a l 2 i , j , i ) (val2_{i,j},i) (val2i,j?,i)
然后重新处理每条边。
对于边 ( u , v , p , q ) (u,v,p,q) (u,v,p,q)，我们在 u u u对应的时间点中二分出离 q q q最近的 v a l 1 u , t val1_{u,t} val1u,t?，建边 ( u , v a l 1 u , t ) → ( v , q ) (u,val1_{u,t})\rightarrow(v,q) (u,val1u,t?)→(v,q)，如果所有的时间点都比 q q q大就不用建了。
然后我们就建出来了一个 D A G DAG DAG，且如果我们按照时间点为关键字来 f o r for for循环更新最短路的话好像就完了？？？
恭喜你有 40 p t s 40pts 40pts 因为有40 p t s pts pts的点是不需要建凸包转移其它边的
那么其它边指的是什么边呢？
考虑到我们之间的建图有个 b u g bug bug，那就是 ( u , v a l 1 u , i ≤ t ) (u,val1_{u,i\le t}) (u,val1u,i≤t?)全部都可以转移给 ( v , q ) (v,q) (v,q)，但是我们只转移了 ( u , v a l 1 u , v a l u , t ) (u,val1_{u,val_{u,t}}) (u,val1u,valu,t??)于是凉凉。
【#|LOJ#3156. 「NOI2019」回家路线（前缀和优化建图+for循环+凸包）】直接暴力建边好像复杂度 O ( m 2 ) O(m^2) O(m2)了啊。。。
于是考虑连边 ( u , v a l 1 u , i ) → ( u , v a l 1 u , i + 1 ) (u,val1_{u,i})\rightarrow(u,val1_{u,i+1}) (u,val1u,i?)→(u,val1u,i+1?)
边权怎么弄？？？
假设我们现在有这两条边 ( u , a ) → ( u , b ) → ( v , c ) (u,a)\rightarrow(u,b)\rightarrow(v,c) (u,a)→(u,b)→(v,c)
那么本来应该是 ( u , a ) → ( v , c )a n d( u , b ) → ( v , c ) (u,a)\rightarrow(v,c)\ and\ (u,b)\rightarrow(v,c) (u,a)→(v,c) and (u,b)→(v,c)
考虑两个之间的差量，不妨设这条边为 ( u , v , t , c ) (u,v,t,c) (u,v,t,c)
那么
( u , a ) → ( v , c ) (u,a)\rightarrow(v,c) (u,a)→(v,c)边权是 A ( c ? a ) 2 + B ( c ? a ) + C A(c-a)^2+B(c-a)+C A(c?a)2+B(c?a)+C
( u , b ) → ( v , c ) (u,b)\rightarrow(v,c) (u,b)→(v,c)边权是 A ( c ? b ) 2 + B ( c ? b ) + C A(c-b)^2+B(c-b)+C A(c?b)2+B(c?b)+C
做个差发现差量是 A ( a 2 ? b 2 ) + B ( b ? a ) + c ? ( 2 A ( b ? a ) ) A(a^2-b^2)+B(b-a)+c*(2A(b-a)) A(a2?b2)+B(b?a)+c?(2A(b?a))
很容易把这个结论拓展到多个点的情况。
然后把 c c c看成一个变量，相当于是一堆 A ′ + B ′ c A' +B' c A′+B′c取最小值，这很凸包。
我们把 ( u , b ) (u,b) (u,b)连出去的所有点按照这个 t t t排序，把 ( u , x 1 ) , ( u , x 2 ) , . . . , ( u , b ) (u,x_1),(u,x_2),...,(u,b) (u,x1?),(u,x2?),...,(u,b)对应的二元组拿来建个凸包就行啦。
代码：

#include #define ri register int #define fi first #define se second using namespace std; typedef long long ll; const int rlen=1<<18|1; inline char gc(){ static char buf[rlen],*ib,*ob; (ib==ob)&&(ob=(ib=buf)+fread(buf,1,rlen,stdin)); return ib==ob?-1:*ib++; } inline int read(){ int ans=0; char ch=gc(); while(!isdigit(ch))ch=gc(); while(isdigit(ch))ans=((ans<<2)+ans<<1)+(ch^48),ch=gc(); return ans; } typedef pair pii; typedef pair pil; typedef pair pll; const int N=2e5+5,M=4e5+5,K=1005; int n,m,A,B,C,tot=0; struct Node{ int v; pll w; friend inline bool operator<(const Node&a,const Node&b){return a.w.fi>b.w.fi; } }; struct edge{int u,v,p,q; }E[M]; Node trans[M<<1]; bool oktrans[M<<1]; ll dis[M<<1]; vectore[M<<1]; setvis[K],tim[N]; vectora[M<<1]; typedef set::iterator It; inline pll operator+(const pll&a,const pll&b){return pll(a.fi+b.fi,a.se+b.se); } struct pot{ ll x,y; pot(ll x=0,ll y=0):x(x),y(y){} friend inline pot operator-(const pot&a,const pot&b){return pot(a.x-b.x,a.y-b.y); } friend inline ll operator^(const pot&a,const pot&b){return a.x*b.y-a.y*b.x; } }ap[K<<1]; int top,q[K<<1],mxtim=0; inline void build(vectora){ top=0; int m=a.size(); for(ri i=0; i1&&((ap[i]-ap[q[top]])^(ap[q[top]]-ap[q[top-1]]))>=0)--top; q[++top]=i; } for(ri i=1; i<=top; ++i)ap[i]=ap[q[i]]; } inline ll calc(pot a,ll b){return a.x*b+a.y; } inline bool operator<(const pii&a,const pii&b){return a.se>b.se; } const int mogic=1e6+7; inline bool operator==(const pii&a,const pii&b){return a.fi==b.fi&&a.se==b.se; } struct Hash_table1{ vectorori[mogic]; vectorval[mogic]; inline void update(pii x,int c){ int t=(x.fi*1000+x.se)%mogic; ori[t].push_back(x); val[t].push_back(c); } inline int query(pii x){ int t=(x.fi*1000+x.se)%mogic; for(ri i=ori[t].size(); ~i; --i)if(ori[t][i]==x)return val[t][i]; } }idx; struct Hash_table2{ vectorori[mogic]; vectorval[mogic]; inline void update(int x,pii c){ int t=x%mogic; ori[t].push_back(x); val[t].push_back(c); } inline pii query(int x){ int t=x%mogic; for(ri i=ori[t].size(); ~i; --i)if(ori[t][i]==x)return val[t][i]; } }invidx; bool in[N]; inline void bfs(){ ll ans=1e18; for(ri i=0; i<=tot; ++i)dis[i]=1e18; dis[1]=0; static int pre[N]; for(ri tt=0; tt<=mxtim; ++tt){ if(!vis[tt].size())continue; for(It it=vis[tt].begin(); it!=vis[tt].end(); ++it){ pii p=pii(*it,tt); int id=idx.query(p); if(p.fi==n){ ans=min(ans,dis[id]+tt); continue; } if(oktrans[id]){ int v=trans[id].v; pll w=trans[id].w; if(a[id].size()&&dis[id]<=a[id][0].fi)a[v].push_back(w+pll(dis[id],0)); a[v].push_back(w+pll(dis[id],0)); ri i; for(i=0; i=dis[id]; ++i); for(; idis[id]+w)pre[v]=id; dis[v]=min(dis[v],dis[id]+w); while(curcalc(ap[cur+1],P))++cur; if(top)dis[v]=min(dis[v],calc(ap[cur],P)+w); } } } cout<p)--it; e[idx.query(pii(u,*it))].push_back((Node){idx.query(pii(v,q)),pll(p,(ll)A*(p-*it)*(p-*it)+(ll)B*(p-*it)+(ll)C)}); } bfs(); return 0; }

    推荐阅读


    上一篇：stm32f7 CAN: loop-back communication on CAN1 and CAN2

    下一篇：Zigbee学习