📝 문제 정보#
🧐 관찰 및 접근#
- 동전들을 swap해서 잘 옮겨서 맞춰야한다..
- 일단 색을 모두 신경쓰긴 싫으니까, 1의 위치를 맞춘다고만 생각하자.
- 뭔가 이분그래프적으로 생각할 수 있지 않을까?
- 이게 움직이는것만 신경쓰면 플로이드워셜 + 이분그래프 매칭 최소비용…으로 하면 되는거같은데?
- 근데 swap이다보니 이렇게 맘대로 하는것보다 효율적인 방법이 무시될 것 같다.
- 일단 이분그래프로 생각을 좀 해보긴 하자. 그림을 그려보자.
- ![[Drawing 2026-03-07 15.31.09.excalidraw.png]]
- 그림 1의 예시이다. 어우 난잡해 ㅋㅋ
- 뭔가 증가경로 맛처럼 할 수 있는거같기는 한데..
- ….가 아니라 그냥 이상태로 최소비용 최대유량 아닌가? 끝이네?
- 이분그래프로 분할할 필요도 없이, 그냥 유량으로 달리면 된다.
💻 풀이#
- 코드 (C++):
void solve(){
int N, M; cin >> N >> M;
MinCostMaxFlow MCMF(N+2);
MCMF.setST(0, N+1);
rep(i, 0, M){
int u, v; cin >> u >> v;
MCMF.add(u, v, 1e9, 1);
MCMF.add(v, u, 1e9, 1);
}
rep(i, 1, N+1){
int x; cin >> x;
if(x == 1) MCMF.add(0, i, 1, 0);
}
rep(i, 1, N+1){
int x; cin >> x;
if(x == 1) MCMF.add(i, N+1, 1, 0);
}
cout << MCMF.match() << '\n';
}