问题
매칭이란, 정점이 겹치지 않도록 간선을 고르는 것을 뜻한다. 즉, 정점 하나당 최대 하나의 매칭된 간선에 연결되어 있을 수 있다. 그 중에서도 매칭된 간선의 개수를 최대화하는 문제를 최대 매칭이라고 부른다.
여러분은 아마 이분 그래프에서의 최대 매칭은 한번쯤 풀어봤을 것이다.
일반 그래프에서의 최대 매칭은 Blossom Algorithm이라는 것을 통해 구할 수 있지만, 이해하기도 어렵고 구현하기는 더 어렵다.
이번에는 거의 일반 그래프에서 매칭 문제를 풀 것이다. 거의 일반 그래프란, 정점 번호의 차이가 A 또는 B인 간선만 존재하는 그래프이다. 구체적으로 Ui와 Vi(Ui<Vi)를 잇는 간선이 있다면, Vi-Ui=A이거나 Vi-Ui=B이다.
하지만 이렇게 문제를 낸다면 아마 인터넷에서 Blossom Algorithm을 복붙하는 친구들이 있을 것 같아, 최대 매칭 대신 매칭의 개수를 구해보도록 한다.
주어진 거의 일반 그래프에서 매칭의 개수를 구하여라. 최대 매칭이 아니어도 됨에 유의하라.
输入
첫 줄에 N(3<=N<=200), M(1<=M<=400), A, B(1<=A<B<N)이 주어진다.
다음 줄부터 M개의 줄에 걸쳐 간선 정보 Ui, Vi(1<=Ui<Vi<=N)이 주어진다.
이때 Vi-Ui는 항상 A 또는 B이다.
输出
매칭의 개수를 구하여라.
示例 #1
4 3 1 2
1 2
1 3
3 4
5
示例 #2
10 14 2 4
5 7
7 9
2 6
6 8
1 5
3 7
4 8
1 3
4 6
8 10
3 5
5 9
2 4
6 10
225
需要登录才能编写代码。