ther203   2년 전

대부분이 아시다시피 짝 홀수 나누어서 이분매칭으로 풀었는데요...


80%쯤에서 계속 틀렸다고 나오네요...

반례는 도저히 못 찾겠어서 시행착오로 틀린원인을 찾았는데요 

이게 왜 원인인지를 모르겠어요


여기서 edegelist는 이분매칭을 하기 위해 필요한 짝홀수간 연결 상태(즉 더해서 소수가 되는 상태)를 나타내는 데이터 구조입니다.

가량 {4,5,7,10,11,12}가 입력된 경우 edgelist는

4->7

10->7

12->5,7,11

로 만들어집니다.

makeMatchingList 함수에서 

 

vector<int>::iterator firstIt = edgeList[first].begin();

while (firstIt != edgeList[first].end()) {
      map<int, int> matchingPair;
      bool flag = true;

      map<int, vector<int>>::iterator mit = edgeList.begin();
       while (mit!=edgeList.end()) {
                if (mit->first != first) {
                             map<int, int> visited;
                              if (!PairMatching(*firstIt, mit->first, edgeList, visited, matchingPair)) {
                                      flag = false;
                                      break;
                              }

                  }

                  mit++;
       }

       if (flag) {
              matchingList.push_back(*firstIt);
       }

        firstIt++;
}

밑 줄친 부분을
아래와 같이 변경하면 맞습니다. 

vector<int>::iterator firstIt = edgeList[first].begin();

while (firstIt != edgeList[first].end()) {       

      map<int, int> matchingPair;      

      int flag = 1;

      map<int, vector<int>>::iterator mit = edgeList.begin();        

      while (mit!=edgeList.end()) {                 

                     if (mit->first != first) {                              

                                  map<int, int> visited;                               

                                  if (PairMatching(*firstIt, mit->first, edgeList, visited, matchingPair))  flag++;

                     }

                  mit++;        

      }

       if (flag==num/2)  matchingList.push_back(*firstIt);    

        firstIt++; 

}


(이 때 num은 총 입력의 갯수 N과 같습니다.)

위와 같이 수정하면 됩니다. 

이분 매칭에서 중간에 한 번이라도 짝을 못 찾는 경우가 있으면 

짝을 못 찾은 값은 뒤에 진행상황에 관계없이 짝이 없는 거 아닌가요???


ther203   2년 전

원인을 알았습니다.

공유하고자 메모 남겨둡니다. 

edgeList에 홀수 혹은 짝수(첫번째 입력값이랑 같은 종류의 수들)가 모두 추가 되지 않은 경우 저러한 방식을 보장할 수 없었습니다.

ex) N = 4
입력값으로 2 3 6 9 된 경우 

edgeList에는 
2 ->3, 9 가 추가되고
(6->0, ※ 이부분이 추가되었어야 했는데 그러질 못했네요. )

6은 빠져있는 상태에서 true, false를 판단하게되고, 

결국 잘못된 결과가 나오네요.

즉, 하나의 원소라도 edgeList에서 빠져있으면, 그 원소를 빼고 dfs를 이용한 이분 매칭을 시도하니깐

그 원소는 고려 안하고 나머지만 고려해서 true인지 false인지 판별하네요...

그래서 매칭이 되는 쌍을 셀 수 밖에 없었던 거네요

만약에 true, false를 이용하고 싶다면, edgeList에 첫번째 입력값이랑 같은 종류(홀수 혹은 짝수)의 입력값을 모두 추가해주면 될 거 같습니다.

댓글을 작성하려면 로그인해야 합니다.