2017.11.1 模拟 communicate

2017.11.1 模拟 communicate

​​ 这题要求我们求最短路 前10分送分题 稀疏图直接spfa预处理 然后o1查询即可

然后接下来的30分时树上最短路 只要倍增求lca即可

再接下来是环套树 只要还是同时倍增到环上 然后顺着一个方向遍历一边整个环 然后o1验证两个环的大小即可 我写崩了..

好不容易改对了 忘了从机房带回家了 被还原卡还原了 导致 又写了好久

#include#include#include#include#define N 11000using namespace std;inline char gc(){ static char now[1<<16],*S,*T; if (T==S){T=(S=now)+fread(now,1,1<<16,stdin);if (T==S) return EOF;} return *S++;}inline int read(){ int x=0,f=1;char ch=gc(); while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=gc();} while (ch<='9'&&ch>='0'){x=x*10+ch-'0';ch=gc();} return x*f;}int f[N],flag[N],fa1[N],fa[N][20],sum[N][20],bin[20],Log[N],n,m,k,sum1[N],id[N],h[N],dep[N],circle[N],num,map[1100][1100];struct node{ int y,next,z;}data[(N+1200)<<1];inline void spfa(int u){ queue q;memset(flag,0,sizeof(flag));memset(f,0x3f,sizeof(f));f[u]=0;flag[u]=1;q.push(u); while (!q.empty()){ int x=q.front();q.pop();flag[x]=0; for (int i=h[x];i;i=data[i].next){ int y=data[i].y,z=data[i].z; if (f[x]+z=0;--i) if (fa[x][i]!=fa[y][i]){tmp+=sum[x][i]+sum[y][i];x=fa[x][i];y=fa[y][i];} tmp+=sum[x][0]+sum[y][0]; x=fa[x][0];y=fa[y][0]; return tmp;}int note,st;void dfs1(int x){ flag[x]=1; for (int i=h[x];i;i=data[i].next){ int y=data[i].y;if (fa1[x]==y) continue;fa1[y]=x; if (flag[y]){circle[x]=1;st=y;note=y;break;}dfs1(y);if (note) break; } if (note==x) circle[x]=1,note=0;else if (note) circle[x]=1;}void dfs2(int x){ flag[x]=1; for (int i=h[x];i;i=data[i].next){ int y=data[i].y,z=data[i].z;if (fa[x][0]==y) continue; if (flag[y]) continue; if (circle[y]) dfs2(y);else{ dep[y]=dep[x]+1;fa[y][0]=x;sum[y][0]=z; for (int j=1;j<=Log[dep[y]];++j){ fa[y][j]=fa[fa[y][j-1]][j-1];sum[y][j]=sum[y][j-1]+sum[fa[y][j-1]][j-1]; }dfs2(y); } }}int len;void dfs3(int x){ for (int i=h[x];i;i=data[i].next){ int y=data[i].y,z=data[i].z;if (fa1[x]==y) continue;fa1[y]=x; if (circle[y]) { sum1[id[x]]=sum1[id[x]-1]+z;len+=z;if (!id[y]) {id[y]=id[x]+1;dfs3(y);} } }}inline int lca1(int &x,int &y){ if (dep[x]=0;--i) if (fa[x][i]!=fa[y][i]){ tmp+=sum[x][i]+sum[y][i],x=fa[x][i],y=fa[y][i]; } tmp+=sum[x][0]+sum[y][0]; if (!circle[x]) x=fa[x][0];if (!circle[y]) y=fa[y][0]; return tmp;}int main(){ freopen("communicate.in","r",stdin); n=read();m=read();k=read();Log[0]=-1; for (int i=1;i<=n;++i) Log[i]=Log[i>>1]+1; for (int i=0;i<=Log[n]+1;++i) bin[i]=1<

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。