仿大学网站网页代码,国内校园网站建设,北京ifc大厦,12355能找回智慧团建密码吗前言 百川到海#xff0c;天下归一 解析
线段树优化建图是用于对一个区间的点连边时的优化方法 建一棵in树一棵出树分别往上和下指即可 大概长这样 #xff08;pia的洛谷的照片#xff09;
建树
正常动态开点即可
void build(int k,int l,int r){tr[ktot](tree){0…前言 百川到海天下归一 解析
线段树优化建图是用于对一个区间的点连边时的优化方法 建一棵in树一棵出树分别往上和下指即可 大概长这样 pia的洛谷的照片
建树
正常动态开点即可
void build(int k,int l,int r){tr[ktot](tree){0,0};if(lr){addline(k,l);return;}build(tr[k].ls,l,mid);build(tr[k].rs,mid1,r);addline(k,tr[k].ls);addline(k,tr[k].rs);//printf(k%d l%d r%d ls%d rs%d\n,k,l,r,tr[k].ls,tr[k].rs);return;
}连边
和线段树的通常操作很类似
void add(int k,int l,int r,int x,int y,int o){//printf(add:k%d l%d r%d x%d y%d o%d\n,k,l,r,x,y,o);if(xlry){//printf( o%d k%d\n,o,k);addline(o,k);return;}if(xmid) add(tr[k].ls,l,mid,x,y,o);if(ymid) add(tr[k].rs,mid1,r,x,y,o);return;
}区间对区间连边
不需要对入树和出树两两相连只需要新开一个虚点都对虚点连边即可 这样总的加边数就是单log的
#includebits/stdc.h
using namespace std;
#define ll long long
const int N5e5100;
const int M1e6100;
ll read(){ll x0,f1;char cgetchar();while(!isdigit(c)){if(c-)f-1;cgetchar();}while(isdigit(c)){xx*10(c^48);cgetchar();}return x*f;
}inline void Max(int x,int y){if(xy) xy;}int n;
struct node{int to,nxt,w;
}p[N*205];
int fi[N3],cnt;
inline void addline(int x,int y,int w){//if(w)//printf(%d %d %d\n,x,y,w);p[cnt](node){y,fi[x],w};fi[x]cnt;return;
}
int ls[N3],rs[N3],rin,rout,tot;
#define mid ((lr)1)
void build(int k,int l,int r,int op){ktot;if(lr){//printf((%d %d) k%d ls%d rs%d op%d\n,l,r,k,0,0,op);if(op0) addline(k,l,0);else addline(l,k,0);return;}build(ls[k],l,mid,op);build(rs[k],mid1,r,op);if(op0){addline(k,ls[k],0);addline(k,rs[k],0);}else{addline(ls[k],k,0);addline(rs[k],k,0);}//printf((%d %d) k%d ls%d rs%d op%d\n,l,r,k,ls[k],rs[k],op);return;
}
void add(int k,int l,int r,int x,int y,int o,int op){if(xlry){if(op0) addline(o,k,op);else addline(k,o,op);return;}if(xmid) add(ls[k],l,mid,x,y,o,op);if(ymid) add(rs[k],mid1,r,x,y,o,op);return;
}
int s,m;
int dis[N3],vis[N3];
dequeintq;
int main(){#ifndef ONLINE_JUDGEfreopen(a.in,r,stdin);freopen(a.out,w,stdout);#endifmemset(fi,-1,sizeof(fi));cnt-1;nread();mread();sread();totn;build(rin,1,n,0);build(rout,1,n,1);for(int i1;im;i){int aread(),bread(),cread(),dread();/*for(int ja;jb;j){for(int kc;kd;k){if(jk) continue;addline(j,k,1);addline(k,j,1);} }*/int otot;add(rin,1,n,a,b,o,0);add(rout,1,n,c,d,o,1);otot;add(rin,1,n,c,d,o,0);add(rout,1,n,a,b,o,1);/*find(rout,1,n,a,b,c,d);find(rout,1,n,c,d,a,b);*/}memset(dis,0x3f,sizeof(dis));q.push_back(s);dis[s]0;while(!q.empty()){int nowq.front();q.pop_front();if(vis[now]) continue;vis[now]1;for(int ifi[now];~i;ip[i].nxt){int top[i].to;if(dis[now]p[i].wdis[to]) continue;dis[to]dis[now]p[i].w;if(p[i].w) q.push_back(to);else q.push_front(to);}}for(int i1;in;i) printf(%d\n,dis[i]);
}
/**/
thanks for reading!
