题解 P2542 【[AHOI2005]航线规划】
zhengrunzhe
2018-12-23 00:15:56
### Tarjan:e-dcc缩点+ 树剖+线段树/并查集
### 先说一个比较简单的版本[poj3694 Network](http://poj.org/problem?id=3694)
题意：每次**增加一条边**，求图中**桥的数量**
首先进行一遍Tarjan求出所有的边双联通分量，然后**缩点成树**
得出初始图的桥的数量为树的边数即**tot(边双数量)-1**记作ans0
考虑添加一条边(x,y) (若用dcc[i]表示编号为i所在的双联通分量的编号)
#### 1.dcc[x]==dcc[y]
两点同处于一个边双中，显然不会对图的桥数有影响
#### 2.dcc[x]!=dcc[y]
**dcc[x]与dcc[y]路径上的所有边都不会再是桥**
考虑一种**暴力**的做法
先求出dcc[x]与dcc[y]的lca
然后暴力从dcc[x]暴力一个个跳到lca，跳过的点(除lca)若没有被标记则标记vis[i]=1
在同样地从dcc[y]往上跳，两次过程**标记到的点数则是减少的桥的数量(同时也是当前两点间桥的数量)**记作△ans
每次输出ans0=ans0-△ans
~~不过貌似poj能给过~~
**考虑更加优秀的做法**
每次有可能会跳过已经标记过的点，考虑**并查集**把已经标记过的压缩起来，每次跳的时候直接跳到集合的顶端就行了
另一种做法可以利用**树剖+线段树**，刚开始所有树边权都为1，每次先路径求和，为减少的桥数，然后把路径上的所有边权都改为0
### 现在回到这道题目
题意：每次**断掉一条边**，求**两点间桥数**
同样的，如果离线操作，把所有的操作先存下来，然后**倒序**，**断掉一条边的操作就变成了增加一条边**，就转化成了刚刚的那道题，两点间的桥数便是△ans
首先先建一幅**由没有被断掉的边构成的图**(因为保证无论航线如何被破坏，任意时刻任意两个星球都能够相互到达，所以建出的图一定连通)，进行缩点成树
然后倒序处理每一个操作，这里采用线段树，断边就是加边，路径边权赋0，询问就输出路径和
可以用一个map表示边是否被断掉，由于有重边~~(我一开始没想重边的wa了n编)~~，应存边(a,b)被删去的次数，因为可能有多条(a,b)，对于原图中的每一条边(a,b)，若map[(a,b)]>0(代表这条边会被删去)就把map[(a,b)]--，否则说明这条边不会被删去，就连接(a,b)
```cpp
#include<map>
#include<stack>
#include<cstdio>
#include<algorithm>
using namespace std;
template<class type>inline const void read(type &in)
{
in=0;char ch=getchar();short fh=1;
while (ch<48||ch>57)fh=ch=='-'?-1:fh,ch=getchar();
while (ch>47&&ch<58)in=(in<<3)+(in<<1)+ch-48,ch=getchar();
in*=fh;
}
const int N=3e4+10,M=1e5+10,Q=4e4+10;
int n,m,a[M],b[M];
stack<int>ans;
map<pair<int,int>,int>e;
struct question{int u,v,type;}q[Q]; //存储每个询问信息
class Edge
{
private:
int cnt;
public:
int head[N],to[M<<1],next[M<<1];
inline const void addedge(int u,int v)
{
next[++cnt]=head[u];
head[u]=cnt;
to[cnt]=v;
}
inline const void connect(int u,int v)
{
addedge(u,v);
addedge(v,u);
}
}g,t;
class Double_Connected_Component //边双处理
{
private:
stack<int>s;
int dfn[N],low[N],cnt;
public:
int dcc[N],tot;
protected:
inline const void tarjan(int u,int fa)
{
dfn[u]=low[u]=++cnt;s.push(u);int v;
for (int i=g.head[u];i;i=g.next[i])
if ((v=g.to[i])!=fa)
if (!dfn[v])tarjan(v,u),low[u]=min(low[u],low[v]);
else if (!dcc[v])low[u]=min(low[u],dfn[v]);
if (low[u]!=dfn[u])return;tot++;
do v=s.top(),s.pop(),dcc[v]=tot;while (u!=v);
}
public:
inline const void tarjan()
{
for (int i=1;i<=n;i++)
if (!dfn[i])
tarjan(i,0);
}
inline const void rebuild() //缩点成树
{
for (int i=1;i<=n;i++)
for (int u,v,j=g.head[i];j;j=g.next[j])
if ((u=dcc[i])!=(v=dcc[g.to[j]]))
t.addedge(u,v);
}
}dcc;
class Segment_Tree //线段树(指针)
{
private:
struct tree
{
int sum;
bool tag;
tree *lson,*rson;
inline const void pushup()
{
sum=lson->sum+rson->sum;
}
inline const void cover()
{
tag=1;sum=0;
}
inline const void pushdown()
{
if (!tag)return;
lson->cover();
rson->cover();
tag=0;
}
inline const void update(int l,int r,int L,int R)
{
if (l>R||r<L)return;
if (l>=L&&r<=R)return cover();
pushdown();
int mid=l+r>>1;
lson->update(l,mid,L,R);
rson->update(mid+1,r,L,R);
pushup();
}
inline const int query(int l,int r,int L,int R)
{
if (l>R||r<L)return 0;
if (l>=L&&r<=R)return sum;
pushdown();
int mid=l+r>>1;
return lson->query(l,mid,L,R)+rson->query(mid+1,r,L,R);
}
}memory_pool[N<<2],*tail;
inline const void init()
{
tail=memory_pool;
}
inline tree *spawn()
{
tree *p=tail++;
p->tag=p->sum=0;
p->lson=p->rson=NULL;
return p;
}
public:
tree *root;
inline Segment_Tree(){init();}
inline const void build(tree *&p,int l,int r)
{
p=spawn();
if (l==r)return (void)(p->sum=(l!=1)); //边权转点权，1号点(根节点)上面没有边，权值为0
int mid=l+r>>1;
build(p->lson,l,mid);
build(p->rson,mid+1,r);
p->pushup();
}
}sgt;
class Heavy_Light_Decomposition //树剖
{
private:
int size[N],top[N],fa[N],dep[N],dfn[N],wson[N],cnt;
public:
inline const void dfs(int p)
{
size[p]=1;
for (int i=t.head[p];i;i=t.next[i])
{
int son=t.to[i];
if (son==fa[p])continue;
fa[son]=p;dep[son]=dep[p]+1;
dfs(son);size[p]+=size[son];
if (size[son]>size[wson[p]])wson[p]=son;
}
}
inline const void dfs(int p,int tp)
{
top[p]=tp;dfn[p]=++cnt;
if (wson[p])dfs(wson[p],tp);
for (int son,i=t.head[p];i;i=t.next[i])
if (!dfn[son=t.to[i]])
dfs(son,son);
}
inline const void update(int a,int b)
{
while (top[a]^top[b])
{
if (dep[top[a]]<dep[top[b]])swap(a,b);
sgt.root->update(1,dcc.tot,dfn[top[a]],dfn[a]);
a=fa[top[a]];
}
if (dep[a]>dep[b])swap(a,b);
sgt.root->update(1,dcc.tot,dfn[a]+1,dfn[b]);
}
inline const int query(int a,int b)
{
int ans=0;
while (top[a]^top[b])
{
if (dep[top[a]]<dep[top[b]])swap(a,b);
ans+=sgt.root->query(1,dcc.tot,dfn[top[a]],dfn[a]);
a=fa[top[a]];
}
if (dep[a]>dep[b])swap(a,b);
return ans+sgt.root->query(1,dcc.tot,dfn[a]+1,dfn[b]);
}
}hld;
int main()
{
read(n);read(m);
for (int i=1;i<=m;i++)read(a[i]),read(b[i]);
int qtot;
for (qtot=1;read(q[qtot].type),~q[qtot].type;qtot++)
{
read(q[qtot].u);read(q[qtot].v);
if (q[qtot].type)continue;
e[make_pair(q[qtot].u,q[qtot].v)]++;
e[make_pair(q[qtot].v,q[qtot].u)]++; //无向图，反过来的也要更改
}
for (int i=1;i<=m;i++)
if (e.find(make_pair(a[i],b[i]))!=e.end()&&e[make_pair(a[i],b[i])])
e[make_pair(a[i],b[i])]--,e[make_pair(b[i],a[i])]--;
else g.connect(a[i],b[i]);
dcc.tarjan();dcc.rebuild();
hld.dfs(1);hld.dfs(1,1);
sgt.build(sgt.root,1,dcc.tot);
for (int i=qtot-1;i;i--)
if (q[i].type)ans.push(hld.query(dcc.dcc[q[i].u],dcc.dcc[q[i].v])); //由于是倒序处理，所以输出也要倒过来，因为tarjan缩点的时候会用到栈，干脆也用栈来实现倒序好了
else hld.update(dcc.dcc[q[i].u],dcc.dcc[q[i].v]);
while (ans.size())printf("%d\n",ans.top()),ans.pop();
return 0;
}
```