【BZOJ】2125:最短-サボテン&丸い木
転送ゲート:bzoj 2125
問題解
丸角樹裸問題は、LCAが角点である場合を特殊に検討すればよい.
コード#コード#
問題解
丸角樹裸問題は、LCAが角点である場合を特殊に検討すればよい.
コード#コード#
#include
#define pb(x) push_back((x))
using namespace std;
typedef long long ll;
const int N=2e4+1000;
int n,m,Q,D[N],F[N][16],bin[16];
ll dis[N],st[N],C[N];
int df[N],dfn,sta[N],low[N],top,cnt;
vector<int>g[N];
map<int,ll>mp[N];
int head[N],to[N<<1],nxt[N<<1],w[N<<1],tot;
inline void lk(int u,int v,ll cc)
{to[++tot]=v;nxt[tot]=head[u];head[u]=tot;w[tot]=cc;}
inline void dfs(int x,int fa)
{
int i,j,num,ty,jud=0;
df[x]=low[x]=++dfn;sta[++top]=x;
for(i=g[x].size()-1;i>=0;--i){
j=g[x][i];
if((df[j] && df[j]>df[x]) || (j==fa)) continue;
if(!df[j]){
dfs(j,x);low[x]=min(low[j],low[x]);
if(low[j]>df[x]){
jud=1;
lk(j,x,mp[j][x]);lk(x,j,mp[j][x]);
for(;sta[top]!=x;top--);
}
}else{
ll dd;jud=1;low[x]=min(low[x],df[j]);
cnt++;C[cnt]=mp[j][x];st[x]=C[cnt];
num=0;for(;sta[top-num]!=j;num++){
C[cnt]+=mp[sta[top-num]][sta[top-num-1]];
}
for(;sta[top]!=j;top--){
dd=min(st[sta[top]],C[cnt]-st[sta[top]]);
lk(sta[top],cnt,0);lk(cnt,sta[top],dd);
if(sta[top-1]!=x)
st[sta[top-1]]=st[sta[top]]+mp[sta[top]][sta[top-1]];
}
lk(j,cnt,0);lk(cnt,j,0);
}
}
}
inline void getfa(int x)
{
int i,j;
for(i=1;bin[i]<=D[x];++i)
F[x][i]=F[F[x][i-1]][i-1];
for(i=head[x];i;i=nxt[i]){
j=to[i];if(j==F[x][0]) continue;
D[j]=D[x]+1;dis[j]=dis[x]+w[i];
F[j][0]=x;getfa(j);
}
}
inline int LCA(int x,int y)
{
if(D[x]<D[y]) swap(x,y);
int i,t=D[x]-D[y];
for(i=0;bin[i]<=t;++i)
if( (bin[i]&t) ) x=F[x][i];
for(i=15;x!=y && i>=0;--i)
if(F[x][i]!=F[y][i])
x=F[x][i],y=F[y][i];
return x==y?x:F[x][0];
}
inline ll bs(ll x){return x<0?-x:x;}
inline ll solve(int x,int y,int t)
{
int i,j,ix=x,iy=y;
for(i=15;i>=0;--i)
if(D[F[x][i]]>D[t])
x=F[x][i];
for(i=15;i>=0;--i)
if(D[F[y][i]]>D[t])
y=F[y][i];
ll dd=bs(st[y]-st[x]);
dd=min(dd,C[t]-dd);
return dis[ix]-dis[x]+dis[iy]-dis[y]+dd;
}
int main(){
int i,j,k,ix,iy;ll iz;
scanf("%d%d%d",&n,&m,&Q);cnt=n;
bin[0]=1;for(i=1;i<16;++i) bin[i]=bin[i-1]<<1;
while(m--){
scanf("%d%d%lld",&ix,&iy,&iz);
if(ix==iy) continue;
if(mp[ix].find(iy)!=mp[ix].end()) mp[ix][iy]=mp[iy][ix]=min(mp[ix][iy],iz);
else{mp[ix][iy]=mp[iy][ix]=iz;g[ix].pb(iy);g[iy].pb(ix);}
}
dfs(1,0);
getfa(1);
while(Q--){
scanf("%d%d",&ix,&iy);
k=LCA(ix,iy);
if(k<=n) printf("%lld
",dis[ix]-dis[k]+dis[iy]-dis[k]);
else printf("%lld
",solve(ix,iy,k));
}
}