#C241022D. 火柴
标签（Label）
- LCA
- 割边
网址（Website）
题解（Solution）
$\qquad$可以很容易建出边。这道题的难点就是求出断掉一条割边之后还有哪些边可以连接这两个连通块，发现从断边的角度不好处理，于是考虑每条能连的边会对哪些割边产生贡献。
$\qquad$容易发现，这条边会对自己组成的新环上的割边造成贡献，问题是，如何快速求出这个新环上的割边并计入贡献呢？这个地方其实会联想到在树上求 $\text{LCA}$ 并且计算，我们先考虑原图是一棵树的情况，发现此时可以使用树上差分来维护对这些边的贡献（对于边 $(x,y)$ ，令 h[x]++,h[y]++，h[lca(x,y)]-=2; ），转换到图上，考虑如果建一棵搜索树，我们惊奇的发现，如果当前点不是割边，我们就不会计算树上差分的贡献，如果是割边，当前割边的贡献就是其子结点的和，我们在搜索树上同样可以维护这个值。
$\qquad$那么我们最后只需要再考虑一种特殊情况，即当前边为斜边时，我们只给它换一个方向，能否是原图联通。对于非割边，只要是斜边就能产生 $1$ 的共享；对于割边，我们发现要保证变换方向的斜边能使原图连通，运用类似树剖的方法，记录每个结点的 $\verb!siz!$ 和 $\verb!dfn!$ ，如果点 $y$ 满足 dfn[x]<=dfn[y] && dfn[y]<=dfn[x]+siz[x]-1 ，那么其就在点 $x$ 的子树内，而对于网格图中的斜边 $(x,y)\to(i,j)$ ，由于是从根开始搜索，直接判断点 $(x,j)$ 和点 $(i,y)$ 是否在 $(i,j)$ 的子树内，若一个在一个不在，这说明当前斜边掉方向之后可以保证图联通。
$\qquad$再讲一个优秀的打法，这道题目读入的时候使用的是字符串，每个字符表示一个 $16$ 进制下的数，转换成二进制后每一位代表当前点在右上、右、右下、下四个方向上有无连边，而对于这个 $0\sim 9,\mathrm{A\sim F}$ 范围的字符，判断起来都要花很多行。我们可以直接 $\verb!string str=”0123456789ABCDEF”!$ ，对于字符 $c$ ，直接使用 $\verb!str.find(c)!$ ，返回的位置就是连边情况。
出题者题解
算法分析
求出原图 $G$ 中所有的桥。一条非桥边可以任意移动，下面只考虑移动桥的情况。
任取 $G$ 的一棵 $DFS$ 生成树 $T$，则它包含了全部的桥。对一条桥边 $e$，切断它以后被分成点集了两部分 $V1, V2$，我们要求出有多少条合法的边连接 $V1$ 和 $V2$。考虑两个端点都在 $V1$ 中的边有多少合法，再考虑至少一个端点在 $V1$ 中的边有多少合法，它们的差即为答案。维护 $V1$ 和上述的两个值，插入/删除一个点都可以 $O(1)$ 完成。在 $T$ 上树上启发式合并可以得到一个 $O(nm(\log n + \log m))$ 的算法。
代码（Code）
#include<bits/stdc++.h>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define Rof(i,l,r) for(int i=l;i>=r;i--)
using namespace std;
#define P pair<int,int>
#define int long long
#define x first
#define y second
#define in(x,l,r) (l<=x && x<=r)
inline int rd(){int x;return cin>>x,x;}
const int inf = 0x3f3f3f3f;
const int N = 712;
bool ST;
string str("0123456789ABCDEF");
vector<P> ft[N][N];
int n,m,ans,a[N][N];
int dx[] = {-1,0,1,1};
int dy[] = {1,1,1,0};
int id[N][N],idx=0;
int siz[N][N];
struct LCA{
bitset<N> vst[N];
int cnmdevcpp;
P f[N*N][20];
inline P cmn(P a,P b){return (id[a.x][a.y]<id[b.x][b.y]?a:b);}
inline P lca(int x,int y,int i,int j){
if(x==i && y==j) return {x,y};int a,b;
if((a=id[x][y])>(b=id[i][j])) swap(a,b);
int d = __lg(b-a++);
return cmn(f[a][d], f[b-(1<<d)+1][d]);
}
void dfs(int x,int y,int fx,int fy){
f[id[x][y]=++idx][0] = {fx,fy};
siz[x][y] = vst[x][y] = 1;
for(auto p:ft[x][y]){
int i,j;tie(i,j)=p;
if(vst[i][j]) continue;
dfs(i,j,x,y);
siz[x][y] += siz[i][j];
}
}
void init(){
dfs(1,1,0,0);
For(j,1,20) for(int i=1;i+(1<<j)-1<=idx;i++)
f[i][j] = cmn(f[i][j-1], f[i+(1<<(j-1))][j-1]);
}
}G;
int dfn[N][N], low[N][N], t;
int f[N][N], tot;
void tarjan(int x,int y,int fx,int fy){
dfn[x][y] = low[x][y] = ++t;
for(auto p:ft[x][y]){
int i,j;tie(i,j)=p;
if(tie(i,j) == tie(fx,fy)) continue;
if(!dfn[i][j]){
tarjan(i,j,x,y), low[x][y] = min(low[x][y], low[i][j]);
f[x][y] += f[i][j];
if(dfn[x][y] < low[i][j]){//求出割边，统计答案
ans += f[i][j];
if(x^i && y^j){//判断自己这条斜边换方向的时候会不会影响连通性
int a,b,c,d;tie(a,b,c,d)=tie(x,j,i,y);
bool f1 = in(id[a][b], id[i][j], id[i][j]+siz[i][j]-1);
bool f2 = in(id[c][d], id[i][j], id[i][j]+siz[i][j]-1);
if(f1^f2) ans++;
}
}else ans += tot + (x^i && y^j);
}else{
low[x][y] = min(low[x][y], dfn[i][j]);//这条边不是割边
if(dfn[x][y] > dfn[i][j]){//只考虑指向祖先的边（边是双向的）
ans += tot;//它可以放在任何一个可以放的位置
if(x^i && y^j) ans++;//如果是斜边，自己调个方向也可以
}
}
}
}
void Solve(){
n = rd(), m = rd();
For(i,1,n){
string s;cin>>s;s = " "+s;
For(j,1,m){
a[i][j] = str.find(s[j]);
For(k,0,3) if((a[i][j]>>k)&1){//枚举4个方向
int x=i+dx[k], y=j+dy[k];
ft[i][j].emplace_back(x,y);
ft[x][y].emplace_back(i,j);
}
}
}G.init();
For(i,1,n) For(j,1,m) For(k,0,3){
if(a[i][j]>>k&1) continue;
int x=i+dx[k], y=j+dy[k];
if(!(in(x,1,n) && in(y,1,m))) continue;
if(k==0 && a[x][j]>>2&1) continue;//斜边的情况
if(k==2 && a[x][j]>>0&1) continue;
tot ++;
f[i][j]++, f[x][y]++;
int fx,fy;tie(fx,fy)=G.lca(i,j,x,y);
f[fx][fy] -= 2;
}tarjan(1,1,0,0), printf("%lld\n",ans);
}
bool ED;
signed main(){
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cerr<<abs(&ST-&ED)/1024./1024.<<"MB\n";
freopen("match.in", "r", stdin);
freopen("match.out", "w", stdout);
int T = 1, Tim = clock();
while(T--) Solve();
return cerr<<"TIME:"<<(clock()-Tim)/1000.,0;
}
