[CSP-J 2019 江西] 道路拆除

知识点

无权图最短路、广度优先搜索、路径合并

解题思路

分别从首都1、s1、s2做BFS，得到距离d0、d1、d2。枚举两条保留路径最后一个公共点v。若d0[v]+d1[v]≤t1且d0[v]+d2[v]≤t2，则可以保留三段最短路的并集，所用边不超过d0[v]+d1[v]+d2[v]。取该和值的最小值，再用m减去它；不存在可行点则输出-1。

正确性说明

任一可行保留子图可取一棵从首都出发的BFS树，树上到两目标的距离不增。在树中两路径有唯一公共前缀，设分叉点为v，其边并集大小为三段路径长度之和；用原图的最短距离替代不会更长，且仍满足时限。因此枚举得到的最小和值不大于最优保留边数。反之，每个可行v的三段最短路并集都是可行方案，边数不超过该和值，故最优保留边数不大于最小和值，两者相等。

易错点

道路是双向的；不可达距离不能参与相加；目标允许相同，时限允许0；不要求保留所有城市的连通性。

复杂度

时间O(n+m)，空间O(n+m)，只需三次BFS。

参考代码（GNU C++17）

#include<bits/stdc++.h>
using namespace std;
int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int n,m;cin>>n>>m;vector<vector<int>>g(n+1);for(int i=0,u,v;i<m;i++){cin>>u>>v;g[u].push_back(v);g[v].push_back(u);}int s1,t1,s2,t2;cin>>s1>>t1>>s2>>t2;auto bfs=[&](int s){vector<int>d(n+1,-1);queue<int>q;d[s]=0;q.push(s);while(!q.empty()){int u=q.front();q.pop();for(int v:g[u])if(d[v]<0)d[v]=d[u]+1,q.push(v);}return d;};auto a=bfs(1),b=bfs(s1),c=bfs(s2);int best=INT_MAX;for(int v=1;v<=n;v++)if(a[v]>=0&&b[v]>=0&&c[v]>=0&&a[v]+b[v]<=t1&&a[v]+c[v]<=t2)best=min(best,a[v]+b[v]+c[v]);cout<<(best==INT_MAX?-1:m-best)<<'\n';}