[AHOI 2005] 航线规划
2024-08-30 13:22:49
[题目链接]
https://www.lydsy.com/JudgeOnline/problem.php?id=1969
[算法]
首先离线 ， 将删边操作转化为加边操作
不妨首先将这张图按边-双连通分量(e-DCC)缩点 ， 缩点后形成了一棵树
树链剖分 + 线段树即可
时间复杂度 : O(NlogN ^ 2)
[代码]
#include<bits/stdc++.h>
using namespace std;
#define MAXN 200010 struct query
{
int type , u , v;
} que[MAXN];
struct edge
{
int to , nxt;
} e[MAXN << ] , ec[MAXN << ]; int n , m , timer , cnt , tot , q , len;
int head[MAXN] , chead[MAXN] , low[MAXN] , dfn[MAXN] , belong[MAXN] ,
size[MAXN] , fa[MAXN] , son[MAXN] , top[MAXN] , depth[MAXN] , u[MAXN] , v[MAXN] , ans[MAXN];
map< pair<int , int> , int> mp;
bool is_bridge[MAXN << ] , des[MAXN << ]; template <typename T> inline void chkmax(T &x,T y) { x = max(x,y); }
template <typename T> inline void chkmin(T &x,T y) { x = min(x,y); }
template <typename T> inline void read(T &x)
{
T f = ; x = ;
char c = getchar();
for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
for (; isdigit(c); c = getchar()) x = (x << ) + (x << ) + c - '';
x *= f;
}
struct Segment_Tree
{
struct Node
{
int l , r , sum;
int tag;
} Tree[MAXN << ];
inline void build(int index , int l , int r)
{
Tree[index].l = l;
Tree[index].r = r;
Tree[index].tag = ;
if (l == r)
{
if (l != ) Tree[index].sum = ;
return;
}
int mid = (l + r) >> ;
build(index << , l , mid);
build(index << | , mid + , r);
update(index);
}
inline void pushdown(int index)
{
Tree[index << ].sum = Tree[index << | ].sum = ;
Tree[index << ].tag = Tree[index << | ].tag = ;
Tree[index].tag = ;
}
inline void update(int index)
{
Tree[index].sum = Tree[index << ].sum + Tree[index << | ].sum;
}
inline void modify(int index , int l , int r)
{
if (Tree[index].l == l && Tree[index].r == r)
{
Tree[index].sum = ;
Tree[index].tag = ;
return;
}
if (Tree[index].tag) pushdown(index);
int mid = (Tree[index].l + Tree[index].r) >> ;
if (mid >= r) modify(index << , l , r);
else if (mid + <= l) modify(index << | , l , r);
else
{
modify(index << , l , mid);
modify(index << | , mid + , r);
}
update(index);
}
inline int query(int index , int l , int r)
{
if (Tree[index].l == l && Tree[index].r == r)
return Tree[index].sum;
if (Tree[index].tag) pushdown(index);
int mid = (Tree[index].l + Tree[index].r) >> ;
if (mid >= r) return query(index << , l , r);
else if (mid + <= l) return query(index << | , l , r);
else return query(index << , l , mid) + query(index << | , mid + , r);
}
} SGT;
inline void addedge(int u , int v)
{
++tot;
e[tot] = (edge){v , head[u]};
head[u] = tot;
}
inline void addcedge(int u , int v)
{
++tot;
ec[tot] = (edge){v , chead[u]};
chead[u] = tot;
}
inline void tarjan(int u , int t)
{
low[u] = dfn[u] = ++timer;
for (int i = head[u]; i; i = e[i].nxt)
{
int v = e[i].to;
if (!dfn[v])
{
tarjan(v , i);
chkmin(low[u] , low[v]);
if (low[v] > dfn[u])
is_bridge[i] = is_bridge[i ^ ] = true;
} else if (i != (t ^ )) chkmin(low[u] , dfn[v]);
}
}
inline void dfs(int u , int id)
{
belong[u] = id;
for (int i = head[u]; i; i = e[i].nxt)
{
int v = e[i].to;
if (!belong[v] && !is_bridge[i]) dfs(v , id);
}
}
inline void dfs1(int u)
{
size[u] = ;
son[u] = ;
for (int i = chead[u]; i; i = ec[i].nxt)
{
int v = ec[i].to;
if (v == fa[u]) continue;
depth[v] = depth[u] + ;
fa[v] = u;
dfs1(v);
size[u] += size[v];
if (son[u] == || size[v] > size[son[u]]) son[u] = v;
}
}
inline void dfs2(int u , int tp)
{
dfn[u] = ++timer;
top[u] = tp;
if (son[u]) dfs2(son[u] , tp);
for (int i = chead[u]; i; i = ec[i].nxt)
{
int v = ec[i].to;
if (v == fa[u] || v == son[u]) continue;
dfs2(v , v);
}
}
inline void modify(int u , int v)
{
u = belong[u] , v = belong[v];
int tu = top[u] , tv = top[v];
while (tu != tv)
{
if (depth[tu] > depth[tv])
{
swap(u , v);
swap(tu , tv);
}
SGT.modify( , dfn[tv] , dfn[v]);
v = fa[tv]; tv = top[v];
}
if (dfn[u] > dfn[v]) swap(u , v);
if (dfn[u] + <= dfn[v]) SGT.modify( , dfn[u] + , dfn[v]);
}
inline int query(int u , int v)
{
u = belong[u] , v = belong[v];
int tu = top[u] , tv = top[v];
int ret = ;
while (tu != tv)
{
if (depth[tu] > depth[tv])
{
swap(u , v);
swap(tu , tv);
}
ret += SGT.query( , dfn[tv] , dfn[v]);
v = fa[tv]; tv = top[v];
}
if (dfn[u] > dfn[v]) swap(u , v);
if (dfn[u] + <= dfn[v]) ret += SGT.query( , dfn[u] + , dfn[v]);
return ret;
} int main()
{ read(n); read(m);
for (int i = ; i <= m; i++)
{
read(u[i]);
read(v[i]);
mp[make_pair(u[i] , v[i])] = mp[make_pair(v[i] , u[i])] = i;
}
while (true)
{
int C , A , B;
read(C);
if (C == -) break;
read(A); read(B);
if (C == ) des[mp[make_pair(A , B)]] = true;
que[++q].type = C; que[q].u = A; que[q].v = B;
}
tot = ;
for (int i = ; i <= m; i++)
{
if (!des[i])
{
addedge(u[i] , v[i]);
addedge(v[i] , u[i]);
}
}
for (int i = ; i <= n; i++)
if (!dfn[i]) tarjan(i , );
for (int i = ; i <= n; i++)
if (!belong[i]) dfs(i , ++cnt);
tot = ;
for (int i = ; i <= m; i++)
{
if (des[i]) continue;
if (belong[u[i]] != belong[v[i]])
{
addcedge(belong[u[i]] , belong[v[i]]);
addcedge(belong[v[i]] , belong[u[i]]);
}
}
timer = ;
memset(dfn , , sizeof(dfn));
dfs1();
dfs2( , );
SGT.build( , , timer);
for (int i = q; i >= ; i--)
{
if (que[i].type == ) modify(que[i].u, que[i].v);
else ans[++len] = query(que[i].u , que[i].v);
}
reverse(ans + , ans + len + );
for (int i = ; i <= len; i++) printf("%d\n" , ans[i]); return ; }
最新文章
- MFC学习笔记（一）
- 使用MongoDB作为后台数据库的尝试
- 长轮询和Comet
- Ubuntu 查看文件以及磁盘空间大小命令df
- Android源码编译jar包BUILD_JAVA_LIBRARY 与BUILD_STATIC_JAVA_LIBRARY的区别（二）
- DES加密And解密
- vijos 1213:80人环游世界
- redis绑定ip以及启动和查看启动状态
- TypeScript入门知识三（函数新特性）
- 空间搜索（圆范围）中Geohash编码方案和网格编码方案对比探讨
- ASP.NET Core中如何针对一个使用HttpClient对象的类编写单元测试
- server client 套接字连接
- poj3259 Wormholes（Bellman-Ford判断负圈）
- 简单使用metamascara
- 关于Jenkins部署代码权限三种方案
- JAVA记录-WebService开发部署
- BZOJ.2095.[POI2010]Bridges(最大流ISAP 二分 欧拉回路)
- Java数据结构和算法（四）：栈
- 实践 ArcGIS Web 3D
- [lr] 常用快捷键