문제
https://www.acmicpc.net/problem/3295
그래프를 링과 선형으로 분해할 때 간선의 개수가 최대가 되도록 하는 문제이다.
모든 컴퓨터는 최대 하나의 다른 컴퓨터와 연결될 수 있다. 컴퓨터 집합 X에 대해 X에서 X로 가는 대응 관계를 생각해보면 전형적인 이분매칭 문제로 풀 수 있다.
각 컴퓨터 하나씩 연결해보자.
코드
에드몬드 카프로 구현하면 시간 초과가 난다. dfs로 구현해주자.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
|
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int pre[2020];
vector<int> g[2020];
bool visited[1010];
int dfs(int s){
visited[s] = true;
for(int nxt : g[s]){
if(pre[nxt] == –1 || (!visited[pre[nxt]] && dfs(pre[nxt]))){
pre[nxt] = s;
return 1;
}
}
return 0;
}
int main(){
int T; scanf(“%d”, &T);
while(T––){
int n, m; scanf(“%d %d”, &n, &m);
for(int i = 0; i < m; i++){
int u, v; scanf(“%d %d”, &u, &v);
v += n;
g[u].push_back(v);
}
memset(pre, –1, sizeof(pre));
int match = 0;
for(int i = 0; i < n; i++){
memset(visited, false, sizeof(visited));
match += dfs(i);
}
printf(“%d\n”, match);
for(int i = 0; i < 2*n; i++) g[i].clear();
}
}
|
cs |
Leave a Reply
Your email is safe with us.