Problem Link

题目大意

给定 $n$ 个点 $m$ 条边的无向图，构造一张边数最少的图使得 $\forall (u,x)$，两图中同时存在或不存在 $1\to u$ 长度为 $x$ 的路径。

数据范围：$n\le 10^5,m\le 2\times 10^5$。

思路分析

由于我们可以在同一条边上来回移动，那么只要到每个点奇数长度和偶数长度最短路相同即可。

设这两条最短路为 $(x,y)$，其中 $x<y$，那么这样的一个点只能和 $(x-1,y-1)$ 连接，或者同时连接 $(x+1,y-1),(x-1,y+1)$。

特别的，如果 $y=x+1$，那么连接另一个 $(x,y)$ 以及一个 $(x-1,y+1)$。

我们可以把所有点按 $x+y$ 分组，同一组内的问题相对独立，按 $x$ 从小到大扫描：

首先如果存在 $(x-1,y-1)$ 那么优先连接肯定更优，否则连接 $(x-1,y+1)$ 和 $(x+1,y-1)$。

如果 $(x+1,y-1)$ 已经和当前点连接，那么继续连接 $(x-1,y+1)$ 而非 $(x-1,y-1)$，因为此时不断连接到 $(x,x+1)$，只需要一条边就能解决两个点。

模拟上述过程即可，注意特判二分图和 $1$ 有自环的情况。

时间复杂度 $\mathcal O(n\log n)$。

代码呈现

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+5,inf=1e9;
vector <int> G[MAXN];
map <int,int> f[MAXN],g[MAXN];
int n,m,d[MAXN][2];
void solve() {
	scanf("%d%d",&n,&m);
	for(int i=0;i<=n;++i) f[i].clear(),g[i].clear(),G[i].clear(),d[i][0]=d[i][1]=inf;
	for(int i=1,u,v;i<=m;++i) scanf("%d%d",&u,&v),G[u].push_back(v),G[v].push_back(u);
	queue <array<int,2>> Q; d[1][0]=0,Q.push({1,0});
	while(Q.size()) {
		int u=Q.front()[0],r=Q.front()[1]^1; Q.pop();
		for(int v:G[u]) if(d[v][r]==inf) d[v][r]=d[u][r^1]+1,Q.push({v,r});
	}
	if(d[1][1]==inf) return printf("%d\n",n-1),void();
	if(d[1][1]==1) return printf("%d\n",n),void();
	vector <array<int,2>> P;
	for(int i=1;i<=n;++i) {
		int x=min(d[i][0],d[i][1]),y=max(d[i][0],d[i][1]);
		if(!f[x][y]++&&i>1) P.push_back({x+y,x});
	}
	int ans=0;
	sort(P.begin(),P.end());
	for(auto it:P) {
		int x=it[1],y=it[0]-it[1],sz=f[x][y],pr=g[x-1][y+1];
		ans+=max(0,sz-pr); //to right or up
		if(f[x-1][y-1]) sz=min(sz,pr);
		ans+=(y==x+1?(sz+1)/2:g[x][y]=sz); //to left
	}
	printf("%d\n",ans);
}
signed main() {
	int _; scanf("%d",&_);
	while(_--) solve();
	return 0;
}