Codeforces - Two Fairs
12897 단어 도론bfsCodeforces
Two fairs are currently taking place in Berland — they are held in two different cities a and b (1≤a,b≤n; a≠b).
Find the number of pairs of cities x and y (x≠a,x≠b,y≠a,y≠b) such that if you go from x to y you will have to go through both fairs (the order of visits doesn’t matter). Formally, you need to find the number of pairs of cities x,y such that any path from x to y goes through a and b (in any order).
Print the required number of pairs. The order of two cities in a pair does not matter, that is, the pairs (x,y) and (y,x) must be taken into account only once.
Input The first line of the input contains an integer t (1≤t≤4⋅104) — the number of test cases in the input. Next, t test cases are specified.
The first line of each test case contains four integers n, m, a and b (4≤n≤2⋅105, n−1≤m≤5⋅105, 1≤a,b≤n, a≠b) — numbers of cities and roads in Berland and numbers of two cities where fairs are held, respectively.
The following m lines contain descriptions of roads between cities. Each of road description contains a pair of integers ui,vi (1≤ui,vi≤n, ui≠vi) — numbers of cities connected by the road.
Each road is bi-directional and connects two different cities. It is guaranteed that from any city you can pass to any other by roads. There can be more than one road between a pair of cities.
The sum of the values of n for all sets of input data in the test does not exceed 2⋅105. The sum of the values of m for all sets of input data in the test does not exceed 5⋅105.
Output Print t integers — the answers to the given test cases in the order they are written in the input.
Example inputCopy 3 7 7 3 5 1 2 2 3 3 4 4 5 5 6 6 7 7 5 4 5 2 3 1 2 2 3 3 4 4 1 4 2 4 3 2 1 1 2 2 3 4 1 outputCopy 4 0 1
제목의 대의: 몇 가지 옳은 점을 찾아내고 한 점을 만족시키면 다른 점까지 반드시 a, b 두 점을 지나갈 것이다.조건에 맞는 점 쌍 수를 출력합니다.
그래서 우리는 반드시 a를 통과해야만 b에 도착할 수 있는 개수와 반드시 b를 통과해야만 a에 도착할 수 있는 개수를 찾아야 한다.그리고 곱하면 된다.
어떻게 구하지?반드시 a를 통과해야만 b에 도착할 수 있다. 실제로 우리는 b점에 대해 bfs를 뛴 다음에 a점을 통과할 수 없도록 제한한다. 그러면 도착하지 못하는 점이 얼마나 많은지 보면 된다.후자는 같다.
AC 코드:
#include
#define int long long
using namespace std;
const int N=2e5+10;
int T,n,m,a,b,res,vis[N],cnt;
vector<int> v[N];
inline void add(int a,int b){v[a].push_back(b); v[b].push_back(a);}
inline int bfs(int x,int y){
queue<int> q; q.push(x); cnt=2; memset(vis,0,8*(n+1)); vis[x]=vis[y]=1;
while(q.size()){
int u=q.front(); q.pop();
for(int i=0,to;i<v[u].size();i++){
to=v[u][i];
if(!vis[to]) vis[to]=1,q.push(to),cnt++;
}
}
return n-cnt;
}
signed main(){
ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
cin>>T;
while(T--){
cin>>n>>m>>a>>b;
for(int i=1,x,y;i<=m;i++) cin>>x>>y,add(x,y);
res=bfs(a,b); res*=bfs(b,a);
cout<<res<<'
';
for(int i=1;i<=n;i++) v[i].clear();
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
HDU 3631 Shortest Path(Floyd + 플러그인)제목: n개의 점 m줄 테두리(단방향 테두리)와 q차 조작을 드리겠습니다. 처음에는 모든 점이 표시가 없습니다. 두 가지 조작이 있습니다. 1.0 x: x를 표시하고 가까이 표시한 경우 "ERROR! At point...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.