CF954D Fight Against Traffic 题解

题目大意

对于一个无向无权联通图 \(G\)，有 \(n\) 个点 \(m\) 条边，往这个图里没有被连接的两个点之间连边，问有多少连法可以使得 \(s\) 到 \(t\) 的最短路长度不变。

解决思路

2.1 暴力做法

可以枚举任意两个点，对于每次连接使用 bfs 求最短路，计算出时间复杂度为 \(O(n^2(n+m))\)，不可通过。

2.2 预处理

如果连接 \(x,y\) 两个点，我们可以通过先从 \(s\) 走到 \(x\) 或 \(y\) 点，再从另一端前往 \(t\) 点，计算出这样走的路线长度。如果这样走的路线长度大于等于两者间的最短路长度（也就是不会使最短路长度变化），那么就将计数器加一。

那我们可以预处理出 \(s\) 点到任何一个点的最短路，用 \(p1_i\) 表示。

再预处理出任意一点到 \(t\) 点的最短路，由于这是无向图，等同于求出 \(t\) 点到任意一点的最短路，用 \(p2_i\) 表示。

最后枚举两个点 \(x,y\)，计算 \(p1_x+p2_y\) 和 \(p1_y+p2_x\)，再和 \(p1_t\) 或者 \(p2_s\) 比较（这两者是等价的，下文中都使用 \(p1_t\)）。如果 \(p1_t \leqslant p1_x+p2_y+1 \ \land \ p1_t \leqslant p1_y+p2_x+1\) 就让计数器变量加一。

代码实现

3.1 建图

采用邻接表建无向图：

for(int i=1;i<=m;i++){
	int a1,a2;
	cin>>a1>>a2;
	l[a1].push_back(a2);
	l[a2].push_back(a1);//无向图建图
    bol[a1][a2]=1;
	bol[a2][a1]=1;//表示a1和a2间有了一条边
}

这里的 \(l\) 是邻接表。

3.2 bfs 预处理最短路

q1.push(s);
p1[s]=0;
ok1[s]=1; //状态初始化，起点为s
while(!q1.empty()){
	int x=q1.front();
	q1.pop();
	for(int i=0;i

for(int i=1;i<=n;i++){
	for(int j=i+1;j<=n;j++){
		if(bol[i][j]){//排除掉有边的情况，这就是建图时多存储一个bool数组的作用
			continue;
		}
		if((p1[i]+p2[j])+1>=p1[t]&&(p2[i]+p1[j])+1>=p1[t]){//比较
			cnt++;//如果这条新路的长度比原最短路长，计数器加一
		}
	}
}