P2542 [AHOI2005]航线规划
题目描述
对Samuel星球的探险已经取得了非常巨大的成就，于是科学家们将目光投向了Samuel星球所在的星系——一个巨大的由千百万星球构成的Samuel星系。
星际空间站的Samuel II巨型计算机经过长期探测，已经锁定了Samuel星系中许多星球的空间坐标，并对这些星球从1开始编号1、2、3……。
一些先遣飞船已经出发，在星球之间开辟探险航线。
探险航线是双向的，例如从1号星球到3号星球开辟探险航线，那么从3号星球到1号星球也可以使用这条航线。
例如下图所示：
![洛谷 P2542 [AHOI2005]航线规划 解题报告](https://image.shishitao.com:8440/aHR0cHM6Ly9iYnNtYXguaWthZmFuLmNvbS9zdGF0aWMvTDNCeWIzaDVMMmgwZEhCekwybHRZV2RsY3pJd01UZ3VZMjVpYkc5bmN5NWpiMjB2WW14dlp5OHhNemswTkRFNUx6SXdNVGd3Tmk4eE16azBOREU1TFRJd01UZ3dOakkwTVRreE9EQTVNVFl5TFRrM09URTBOVEkxTVM1d2JtYz0uanBn.jpg?w=700&webp=1 "洛谷 P2542 [AHOI2005]航线规划 解题报告")
在5个星球之间，有5条探险航线。
A、B两星球之间，如果某条航线不存在，就无法从A星球抵达B星球，我们则称这条航线为关键航线。
显然上图中，1号与5号星球之间的关键航线有1条：即为4-5航线。
然而，在宇宙中一些未知的磁暴和行星的冲撞，使得已有的某些航线被破坏，随着越来越多的航线被破坏，探险飞船又不能及时回复这些航线，可见两个星球之间的关键航线会越来越多。
假设在上图中，航线4-2（从4号星球到2号星球）被破坏。此时，1号与5号星球之间的关键航线就有3条：1-3，3-4，4-5。
小联的任务是，不断关注航线被破坏的情况，并随时给出两个星球之间的关键航线数目。现在请你帮助完成。
输入输出格式
输入格式：
第一行有两个整数N，M。表示有N个星球（1< N < 30000），初始时已经有M条航线（1 < M < 100000）。随后有M行，每行有两个不相同的整数A、B表示在星球A与B之间存在一条航线。接下来每行有三个整数C、A、B。C为1表示询问当前星球A和星球B之间有多少条关键航线；C为0表示在星球A和星球B之间的航线被破坏，当后面再遇到C为1的情况时，表示询问航线被破坏后，关键路径的情况，且航线破坏后不可恢复； C为-1表示输入文件结束，这时该行没有A,B的值。被破坏的航线数目与询问的次数总和不超过40000。
输出格式：
对每个C为1的询问，输出一行一个整数表示关键航线数目。
说明
我们保证无论航线如何被破坏，任意时刻任意两个星球都能够相互到达。在整个数据中，任意两个星球之间最多只可能存在一条直接的航线。
思路：
有一个常见套路：对于删除一些边，采用离线逆序处理。
- 建要删去的边删去
- 对删去后的边进行缩点，得到一颗树
- 问题转化为求两点之间边数
- 逆序连边将处于环上的边权置0，采用树链剖分
细节：因为是点权下放至边权，所以每次不对LCA进行操作
PS：无向图建新图的一个错误我拍了2个小时mmp(居然还有60分)
错误的：
void New()
{
for(int i=1;i<=n0;i++)
for(int j=head0[i];j;j=next0[j])
if(edge0[j]&&ha[i]!=ha[to0[j]])
add(ha[i],ha[to0[j]]),add(ha[to0[j]],ha[i]);
}
正确的：
void New()
{
for(int i=1;i<=n0;i++)
for(int j=head0[i];j;j=next0[j])
if(edge0[j]&&ha[i]!=ha[to0[j]])
add(ha[i],ha[to0[j]]);
}
Code:
#include <cstdio>
#include <cstring>
#include <map>
#define mid (l+r>>1)
#define Mid (L[id]+R[id]>>1)
#define ls id<<1
#define rs id<<1|1
using namespace std;
const int N=30010;
const int M=100010;
int head0[N],cnt0=0,to0[M<<1],next0[M<<1],edge0[M<<1];
void add0(int u,int v,int w)
{
next0[++cnt0]=head0[u];edge0[cnt0]=w;to0[cnt0]=v;head0[u]=cnt0;
}
int head[N],cnt=0,to[M<<1],next[M<<1];
void add(int u,int v)
{
next[++cnt]=head[u];to[cnt]=v;head[u]=cnt;
}
map <int,map <int,int > > del;//要删去的边
int aska[N],askb[N],acnt=0,n0,m,n,ans[N],wcnt,typ[N];
void Delete()
{
for(int i=1;i<=n0;i++)
for(int j=head0[i];j;j=next0[j])
if(del[i][to0[j]])
edge0[j]=0;
}
int s[N],tot=0,time=0,low[N],dfn[N],in[N],ha[N];
void tarjan(int now,int fa)
{
dfn[now]=low[now]=++time;
s[++tot]=now,in[now]=1;
for(int i=head0[now];i;i=next0[i])
{
if(!edge0[i]) continue;
int v=to0[i];
if(!dfn[v])
{
tarjan(v,now);
low[now]=min(low[now],low[v]);
}
else if(in[v]&&v!=fa)
low[now]=min(low[now],dfn[v]);
}
if(dfn[now]==low[now])
{
int tmp;
n++;
do
{
tmp=s[tot--];
in[tmp]=0;
ha[tmp]=n;
}while(tmp!=now);
}
}
void New()
{
for(int i=1;i<=n0;i++)
for(int j=head0[i];j;j=next0[j])
if(edge0[j]&&ha[i]!=ha[to0[j]])
add(ha[i],ha[to0[j]]);
}
int top[N],f[N],ws[N],siz[N],dep[N];
void dfs1(int now)
{
siz[now]++;
for(int i=head[now];i;i=next[i])
{
int v=to[i];
if(f[now]!=v)
{
f[v]=now;
dep[v]=dep[now]+1;
dfs1(v);
siz[now]+=siz[v];
if(siz[ws[now]]<siz[v])
ws[now]=v;
}
}
}
void dfs2(int now,int anc)
{
dfn[now]=++time;
top[now]=anc;
if(!ws[now]) return;
dfs2(ws[now],anc);
for(int i=head[now];i;i=next[i])
if(!dfn[to[i]])
dfs2(to[i],to[i]);
}
int dat[N<<2],L[N<<2],R[N<<2];
void build(int id,int l,int r)
{
dat[id]=(r+1-l);
L[id]=l,R[id]=r;
if(l==r) return;
build(ls,l,mid);
build(rs,mid+1,r);
}
void change(int id,int l,int r)
{
if(!dat[id]) return;
if(L[id]==l&&R[id]==r)
{
dat[id]=0;
return;
}
if(r<=Mid) change(ls,l,r);
else if(l>Mid) change(rs,l,r);
else change(ls,l,Mid),change(rs,Mid+1,r);
dat[id]=dat[ls]+dat[rs];
}
int query(int id,int l,int r)
{
if(!dat[id]) return 0;
if(L[id]==l&&R[id]==r)
return dat[id];
if(r<=Mid) return query(ls,l,r);
else if(l>Mid) return query(rs,l,r);
else return query(ls,l,Mid)+query(rs,Mid+1,r);
}
void t_change(int x,int y)
{
while(top[x]!=top[y])
{
if(dep[top[x]]>dep[top[y]])
{
change(1,dfn[top[x]],dfn[x]);
x=f[top[x]];
}
else
{
change(1,dfn[top[y]],dfn[y]);
y=f[top[y]];
}
}
if(dfn[x]!=dfn[y])
change(1,min(dfn[x],dfn[y])+1,max(dfn[x],dfn[y]));
}
int t_query(int x,int y)
{
int ans=0;
while(top[x]!=top[y])
{
if(dep[top[x]]>dep[top[y]])
{
ans+=query(1,dfn[top[x]],dfn[x]);
x=f[top[x]];
}
else
{
ans+=query(1,dfn[top[y]],dfn[y]);
y=f[top[y]];
}
}
if(dfn[x]!=dfn[y])
ans+=query(1,min(dfn[x],dfn[y])+1,max(dfn[x],dfn[y]));
return ans;
}
int cntt[N];
int main()
{
scanf("%d%d",&n0,&m);
int u,v;
for(int i=1;i<=m;i++)
{
scanf("%d%d",&u,&v);
add0(u,v,1),add0(v,u,1);
}
int a,b,c;
scanf("%d%d%d",&c,&a,&b);
while(2333)
{
aska[++acnt]=a,askb[acnt]=b,typ[acnt]=c;
if(!c)
del[a][b]=1,del[b][a]=1;
scanf("%d",&c);
if(c==-1)
break;
scanf("%d%d",&a,&b);
}
Delete();//删掉访问的边
tarjan(1,0);//缩点
New();//建立新图
memset(dfn,0,sizeof(dfn));
time=0;
dfs1(1);
dfs2(1,1);
build(1,1,n);
for(int i=acnt;i;i--)
{
if(typ[i]) ans[++wcnt]=t_query(ha[aska[i]],ha[askb[i]]);
else t_change(ha[aska[i]],ha[askb[i]]);
}
for(int i=wcnt;i;i--)
printf("%d\n",ans[i]);
return 0;
}
2018.6.24