백준: 14750
</br>
ICPC 2017 지역 예선 문제 중 하나다
쥐를 어떻게 구멍에 넣나를 엄청 고민했는데, 알고 보니 이게 이분 매칭이라고 한다
</br>
14750: Jerry and Tom
https://www.acmicpc.net/problem/14750
일단 문제를 이해하자면,
코너들이 도형을 이루는 순서대로 n개 들어온다.
구멍들이 h개 들어온다. 구멍은 코너들이 이루는 도형의 선 위에 있다.
쥐들이 m개 들어온다. 쥐는 코너들이 이루는 도형의 안에 있다.
쥐가 구멍을 볼 수 있다면 그 쥐는 구멍에 들어갈 수 있다.
각 구멍은 쥐를 최대 k마리 담을 수 있다.
이 때 모든 쥐들이 구멍에 들어갈 수 있을까?? 판단하기
</br>
여기서 일단 쥐가 구멍을 볼 수 있는 조건을 생각해 봐야 한다.
이건 브루트포스로, 도형을 이루는 모든 선분들과 구멍-쥐 선분들이 교차하는지 확인하면 될 것이다.
그런데, 구멍이 선분 위에 있으므로 무조건 구멍이 한 번은 교차한다. 따라서 한 번보다 더 교차하면 쥐는 구멍을 볼 수 없다.
이 때 예외가 하나 있는데, 두 번 교차하는 경우에 쥐가 구멍을 볼 수 있는 경우가 있다.
ex 1)
H-----C
| \ |
| M |
C-----C
ex 2)
C-----C
| |
C---H |
| \ |
| M |
C---------C
이런 경우들이면 총 두 번 교차한다고 판정되지만, 쥐는 구멍을 볼 수 있다.
따라서 만약 선분이 (t, t+1), (t+1, t+2)이고 t+1 == h라면 딱 두 선분의 중간인 그 곳이 구멍이므로 예외 처리를 해 주자
</br>
또 이제 이분 매칭을 생각하면, 구멍-쥐로 생각할지, 쥐-구멍으로 생각할지 고민해 보자
일단 구멍이 담을 수 있는 쥐도 여러 마리고, 쥐가 갈 수 있는 구멍도 여러 개이므로 둘 다 가능하긴 하다
그러나 구멍이 최대 k마리 담을 수 있다는 조건이 있다. 전 포스트(https://cyj893.github.io/algorithm/Algorithm18_14/)에서 본 “열혈강호 2” 문제처럼 생각하면 각 사람이 최대 k개 일을 맡는 것과 같으므로 구멍-쥐로 생각해서 dfs를 k번 돌리면 되겠다.
</br>
교차 판정하기
int sarea(P a, P b, P c){
ll x1 = a.first;
ll y1 = a.second;
ll x2 = b.first;
ll y2 = b.second;
ll x3 = c.first;
ll y3 = c.second;
ll ret = x2*y1 + x3*y2 + x1*y3 - (x1*y2 + x2*y3 + x3*y1);
if( ret < 0 ) return 1;
if( ret == 0 ) return 0;
return -1;
}
bool isCross(P a, P b, P c, P d){
int abc = sarea(a, b, c);
int abd = sarea(a, b, d);
int cda = sarea(c, d, a);
int cdb = sarea(c, d, b);
if( abc*abd <= 0 && cda*cdb <= 0 ){
if( abc*abd == 0 && cda*cdb == 0 ){
if( a > b ) swap(a, b);
if( c > d ) swap(c, d);
if( a <= d && c <= b ) return true;
else return false;
}
else return true;
}
else return false;
}
// in main()
for(int ho = 1; ho <= h; ho++){
for(int mi = 1; mi <= m; mi++){
stack<int> st;
for(int co = 0; co < n; co++){
if( isCross(corners[co], corners[co+1], holes[ho], mice[mi]) ){
st.push(co);
}
if( st.size() >= 3 ) break;
}
if( st.size() >= 3 ) continue;
if( st.size() == 2 ){
int cnt = 0;
int t1 = st.top();
st.pop();
int t2 = st.top();
st.pop();
if( corners[t1+1] == corners[t2] && corners[t2] == holes[ho] ) holeCanGet[ho].push_back(mi);
else if( corners[t2+1] == corners[t1] && corners[t1] == holes[ho] ) holeCanGet[ho].push_back(mi);
}
else if( st.size() == 1 ) holeCanGet[ho].push_back(mi);
}
}
일단 포문으로 각 구멍-쥐마다 모든 선분들을 돌아 본다. 코너 배열은 corners[n] = corners[0];로 순환 구조로 쉽게 포문을 돌게 한다.
만약 교차하는 선분이 있다면 그 인덱스를 스택에 넣어 준다.
그런데 스택의 사이즈가 3 이상이 되면, 쥐는 구멍을 볼 수 없으므로 종료하고 넘어가야 한다.
스택의 사이즈가 2라면, 위에서 말한 특수한 예외인지를 검사하고, 맞다면 현재 쥐를 매칭 가능한 번호에 추가한다.
</br>
이분 매칭
bool dfs(int now){
visited[now] = 1;
for(int i = 0; i < holeCanGet[now].size(); i++){
int nx = holeCanGet[now][i];
if( work[nx] == 0 || (visited[work[nx]] == 0 && dfs(work[nx])) ){
work[nx] = now;
return true;
}
}
return false;
}
// in main()
int ans = 0;
for(int i = 1; i <= h; i++){
for(int kk = 0; kk < k; kk++){
for(int j = 1; j <= h; j++){
visited[j] = 0;
}
if( dfs(i) ) ans++;
}
}
if( ans == m ) cout << "Possible\n";
else cout << "Impossible\n";
각 구멍 마다 k마리 담을 수 있으므로, k번 dfs를 수행한다.
만약 체크된 수가 쥐의 전체 수와 같다면, 성공했으므로 Possible을 출력한다.
</br>
최종 코드
#include <bits/stdc++.h>
#define P pair<long long, long long>
#define ll long long
using namespace std;
vector<int> holeCanGet[251];
P corners[1001];
P holes[51];
P mice[251];
int work[251];
int visited[251];
bool dfs(int now){
visited[now] = 1;
for(int i = 0; i < holeCanGet[now].size(); i++){
int nx = holeCanGet[now][i];
if( work[nx] == 0 || (visited[work[nx]] == 0 && dfs(work[nx])) ){
work[nx] = now;
return true;
}
}
return false;
}
int sarea(P a, P b, P c){
ll x1 = a.first;
ll y1 = a.second;
ll x2 = b.first;
ll y2 = b.second;
ll x3 = c.first;
ll y3 = c.second;
ll ret = x2*y1 + x3*y2 + x1*y3 - (x1*y2 + x2*y3 + x3*y1);
if( ret < 0 ) return 1;
if( ret == 0 ) return 0;
return -1;
}
bool isCross(P a, P b, P c, P d){
int abc = sarea(a, b, c);
int abd = sarea(a, b, d);
int cda = sarea(c, d, a);
int cdb = sarea(c, d, b);
if( abc*abd <= 0 && cda*cdb <= 0 ){
if( abc*abd == 0 && cda*cdb == 0 ){
if( a > b ) swap(a, b);
if( c > d ) swap(c, d);
if( a <= d && c <= b ) return true;
else return false;
}
else return true;
}
else return false;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(NULL);
int n, k, h, m;
cin >> n >> k >> h >> m;
for(int i = 0; i < n; i++){
cin >> corners[i].first >> corners[i].second;
}
corners[n] = corners[0];
for(int i = 1; i <= h; i++){
cin >> holes[i].first >> holes[i].second;
}
for(int i = 1; i <= m; i++){
cin >> mice[i].first >> mice[i].second;
}
for(int ho = 1; ho <= h; ho++){
for(int mi = 1; mi <= m; mi++){
stack<int> st;
for(int co = 0; co < n; co++){
if( isCross(corners[co], corners[co+1], holes[ho], mice[mi]) ){
st.push(co);
}
if( st.size() >= 3 ) break;
}
if( st.size() >= 3 ) continue;
if( st.size() == 2 ){
int cnt = 0;
int t1 = st.top();
st.pop();
int t2 = st.top();
st.pop();
if( corners[t1+1] == corners[t2] && corners[t2] == holes[ho] ) holeCanGet[ho].push_back(mi);
else if( corners[t2+1] == corners[t1] && corners[t1] == holes[ho] ) holeCanGet[ho].push_back(mi);
}
else if( st.size() == 1 ) holeCanGet[ho].push_back(mi);
}
}
// for(int i = 1; i <= h; i++){
// cout<<i<<": ";
// for(int a : holeCanGet[i]){
// cout << a << ' ';
// }
// cout<<endl;
// }
// cout<<endl;
int ans = 0;
for(int i = 1; i <= h; i++){
for(int kk = 0; kk < k; kk++){
for(int j = 1; j <= h; j++){
visited[j] = 0;
}
if( dfs(i) ) ans++;
}
}
if( ans == m ) cout << "Possible\n";
else cout << "Impossible\n";
}
</br>
이분 매칭을 알고 나니 그 부분은 오히려 간단하고 선분 교차 판정 쪽이 까다로운 문제였다
</br>
댓글남기기