题目传送门:abc 309
前面的简单题就不放了
D - Add One Edge
题意:
给你一个无向图图,分为两个连通块,一个顶点数为 n1(1~n1),一个顶点数为 n2(n1+1~n1+n2),图中共有 m 条边。如果现在在两个连通块之间连接一条边,那么顶点 1 与顶点 n1+n2 则相互可达,且对于此种连法,两顶点之间存在一条最短的可达路径。问你在所有的情况中,最短路径的最大值是多少?
思路:
法一:dijkstra
因为问的是最短距离的最大,所以我们首先需要每一个连通块内两顶点到所有点的最短距离,又需要最大的最短距离,所以两个连通块内的最大距离之和+1即为最终答案。
首先利用 dij 处理顶点 1 和顶点 n1+n2 的单源最短路,设顶点 1 所在的连通块与顶点 1 的最远距离为 ans1,顶点 n1+n2 所在的连通块与顶点 n1+n2 的最远距离为ans2,最终的答案即为\(1+ans_1+ans_2\)
注意一点,就是\(0\le n_1+n_2\le 3e5\),注意全局变量的空间大小!
const int maxm=3e5+5,inf=0x3f3f3f3f,mod=998244353;
int n1,n2,m,ans[2];
vector<int> e[maxm],dis(maxm,inf);
vector<int> vis(maxm,false);
void dij(int x,int p){
priority_queue<pii,vector<pii>,greater<pii>> q;
q.push({0,x});
pii t;
while(!q.empty()){
t=q.top();
q.pop();
if(vis[t.second]) continue;
dis[t.second]=t.first;
ans[p]=max(ans[p],t.first);
vis[t.second]=true;
for(auto a:e[t.second]){
if(!vis[a] && dis[a]>t.first+1){
q.push({t.first+1,a});
}
}
}
return ;
}
void solve(){
cin>>n1>>n2>>m;
int a,b;
for(int i=0;i<m;++i){
cin>>a>>b;
e[a].push_back(b);
e[b].push_back(a);
}
dij(1,0);
dij(n1+n2,1);
cout<<ans[0]+ans[1]+1<<'\n';
return ;
}
法二:BFS+队列
其实bfs基本思想与dij相同,利用BFS+队列逐层遍历
const int maxm=3e5+5,inf=0x3f3f3f3f,mod=998244353;
int n1,n2,m,ans[2];
vector<int> e[maxm],dis(maxm,inf);
vector<bool> vis(maxm,false);
void bfs(int x,int p){
dis[x]=0;
queue<int> q;
q.push(x);
int t;
while(!q.empty()){
t=q.front();
q.pop();
vis[t]=true;
for(auto a:e[t]){
if(!vis[a] && dis[a]>dis[t]+1){
dis[a]=dis[t]+1;
ans[p]=max(ans[p],dis[t]+1);
q.push(a);
}
}
}
return ;
}
void solve(){
cin>>n1>>n2>>m;
int a,b;
for(int i=0;i<m;++i){
cin>>a>>b;
e[a].push_back(b);
e[b].push_back(a);
}
bfs(1,0);
bfs(n1+n2,1);
cout<<ans[0]+ans[1]+1<<'\n';
return ;
}
- Beginner AtCoder Contest 309beginner atcoder contest 309 contest programming beginner atcoder beginner atcoder contest 296 beginner atcoder contest 295 beginner atcoder contest abcde beginner atcoder contest 335 beginner atcoder contest 332 beginner atcoder contest 328 beginner atcoder contest 334 beginner atcoder contest 315