wps的ppt做网站超链接,服装鞋帽 网站建设,绵阳个人网站建设,建立网站步骤题目#xff1a;BZOJ4326、洛谷P2680、Vijos P1983、UOJ#150、codevs4632、codevs5440。 题目大意#xff1a;有一棵带权树#xff0c;有一些运输计划#xff0c;第i个运输计划从ai到bi#xff0c;耗时为ai到bi的距离#xff0c;所有运输计划一起开始。现在可以把一条边权…题目BZOJ4326、洛谷P2680、Vijos P1983、UOJ#150、codevs4632、codevs5440。 题目大意有一棵带权树有一些运输计划第i个运输计划从ai到bi耗时为ai到bi的距离所有运输计划一起开始。现在可以把一条边权变成0求最终运输计划最短要多少时间。 解题思路标算是树剖然而我并不会…… 我的方法是LCA二分树上差分。 首先LCA求出每个运输计划的长度可一遍dfs求出每个节点到根的距离dist则a到b的长度为dist[a]dist[b]-(dist[lca(a,b)]1)。 接着二分答案然后判断答案可行性。 对于每一个答案我们要找的是所有长度大于当前答案的运输计划的公共边因为只有所有长度大于当前答案的运输计划全部变成小于等于当前答案当前答案才可行。 用树上差分不懂请百度。我们用s[i]记录i到它父亲这条边有多少计划经过。 对于每个运输计划如果长度大于当前答案我们给s[a]1,s[b]1,s[lca(a,b)]-2因为我们要统计的是边所以对于两个点lca(a,b)对应的边实际是没有走到的所以-2。 差分完后判断答案可行性即可。 我用倍增时间复杂度为$O(m\log_2 n(nm)\log_2 len)$len为运输计划的最大长度。 但常数巨大1s很容易被卡因此有些地方还过不掉。例如我在UOJ上就被卡97。但在时限较宽或数据较弱的地方还是能AC的。 C Code %:pragma GCC optimize(2)
#includecstdio
#includecctype
#includecstring
using namespace std;
char buf[10700005];
int bufpos,n,m,head[300001],deep[300001],p[300001][21],dist[300001],s[300001],fa_edge[300001],mx,now;
struct edge{int to,dis,nxt;
}e[600003];
struct que{int a,b,len,LCA;
}f[300001];
inline int max(int a,int b){return(ab)?a:b;}
inline int readint(){char cbuf[bufpos];for(;!isdigit(c);cbuf[bufpos]);int p0;for(;isdigit(c);cbuf[bufpos])p(p3)(p1)(c^0);return p;
}
void dfs(int s){for(int ihead[s];i;ie[i].nxt)if(!deep[e[i].to]){fa_edge[e[i].to]i;deep[e[i].to]deep[s]1;p[e[i].to][0]s;dist[e[i].to]dist[s]e[i].dis;dfs(e[i].to);}
}
int lca(int x,int y){if(deep[x]deep[y])x^y^x^y;int i;for(i0;(1i)deep[x];i);--i;for(int ji;j-1;--j)if(deep[p[x][j]]deep[y])xp[x][j];if(xy)return x;for(int ji;j-1;--j)if(p[x][j]!-1p[x][j]!p[y][j])xp[x][j],yp[y][j];return p[x][0];
}
void updata(int now){for(int ihead[now];i;ie[i].nxt)if(deep[now]deep[e[i].to]){updata(e[i].to);s[now]s[e[i].to];}
}
bool ok(int ans){memset(s,0,sizeof s);int gz0;for(int i1;in;i)if(f[i].lenans){gz;s[f[i].a];s[f[i].b];s[f[i].LCA]-2;}updata(1);for(int i1;im;i)if(s[i]gzmx-anse[fa_edge[i]].dis)return true;return false;
}
int main(){buf[fread(buf,1,10700000,stdin)]bufpos0;mreadint(),nreadint();for(int i1;im;i){int fromreadint(),toreadint(),disreadint();nowi1;e[now-1](edge){to,dis,head[from]};head[from]now-1;e[now](edge){from,dis,head[to]};head[to]now;}memset(p,-1,sizeof p);dist[1]0;deep[1]1;dfs(1);for(int j1;(1j)m;j)for(int i1;im;i)if(p[i][j-1]!-1)p[i][j]p[p[i][j-1]][j-1];int l0,r0,mid;for(int i1;in;i){f[i].areadint();f[i].breadint();f[i].LCAlca(f[i].a,f[i].b);rmax(r,f[i].lendist[f[i].a]dist[f[i].b]-(dist[f[i].LCA]1));}mxr;r;while(lr){midlr1;if(ok(mid))rmid;elselmid1;}printf(%d\n,r);return 0;
}倍增时间复杂度比较高我改成用Tarjan求LCA速度瞬间变快在UOJ上成功卡了过去。不过codevs4632仍然被卡。 以下为Tarjan代码。 C Code %:pragma GCC optimize(2)
#includecstdio
#includecctype
#includecstring
using namespace std;
char buf[10700005];
int bufpos,n,m,head[300001],deep[300001],dist[300001],s[300001],fa_edge[300001],mx,now,headq[300001],nq0;
bool vis[300001];
int fa[300001];
struct edge{int to,dis,nxt;
}e[600003];
struct que{int a,b,len,LCA;
}f[300001];
struct Query{int same,nxt,to,num;bool flag;
}q[600003];
int find(int x){return(fa[x]x)?x:(fa[x]find(fa[x]));}
inline int max(int a,int b){return(ab)?a:b;}
inline int readint(){char cbuf[bufpos];for(;!isdigit(c);cbuf[bufpos]);int p0;for(;isdigit(c);cbuf[bufpos])p(p3)(p1)(c^0);return p;
}
void dfs(int s){for(int ihead[s];i;ie[i].nxt)if(!deep[e[i].to]){fa_edge[e[i].to]i;deep[e[i].to]deep[s]1;dist[e[i].to]dist[s]e[i].dis;dfs(e[i].to);}
}
void tarjan(int root){for(int ihead[root];i;ie[i].nxt)if(deep[root]deep[e[i].to]){tarjan(e[i].to);fa[e[i].to]root;vis[e[i].to]true;}for(int iheadq[root];i;iq[i].nxt)if(vis[q[i].to]!q[i].flag){q[i].flagq[q[i].same].flagtrue;f[q[i].num].LCAfind(q[i].to);}
}
void updata(int now){for(int ihead[now];i;ie[i].nxt)if(deep[now]deep[e[i].to]){updata(e[i].to);s[now]s[e[i].to];}
}
bool ok(int ans){memset(s,0,sizeof s);int gz0;for(int i1;in;i)if(f[i].lenans){gz;s[f[i].a];s[f[i].b];s[f[i].LCA]-2;}updata(1);for(int i1;im;i)if(s[i]gzmx-anse[fa_edge[i]].dis)return true;return false;
}
int main(){buf[fread(buf,1,10700000,stdin)]bufpos0;mreadint(),nreadint();for(int i1;im;i){int fromreadint(),toreadint(),disreadint();nowi1;e[now-1](edge){to,dis,head[from]};head[from]now-1;e[now](edge){from,dis,head[to]};head[to]now;fa[i]i;}fa[m]m;deep[1]1;dfs(1);int l0,r0,mid;for(int i1;in;i){f[i].areadint();f[i].breadint();int xf[i].a,yf[i].b;q[nq].toy;q[nq].samenq1;q[nq].numi;q[nq].nxtheadq[x];headq[x]nq;q[nq].tox;q[nq].samenq-1;q[nq].numi;q[nq].nxtheadq[y];headq[y]nq;if(xy)q[nq].flagq[nq-1].flagtrue,f[i].LCAx;}tarjan(1);for(int i1;in;i)rmax(r,f[i].lendist[f[i].a]dist[f[i].b]-(dist[f[i].LCA]1));mxr;r;while(lr){midlr1;if(ok(mid))rmid;elselmid1;}printf(%d\n,r);return 0;
}转载于:https://www.cnblogs.com/Mrsrz/p/7635580.html
