글 읽기 - 96%틀렸습니다 질문드립니다

runnie0427 3년 전 0

열혈강호 1이랑 2 풀었던 코드에서 조금 수정했습니다. 이분매칭 자체는 문제 없을 것 같습니다.

그리디하게 할 수 있는 일이 많은 k명에게 일을 두개씩 시켰습니다.

혹시 어떤게 반례인지 알려주실 수 있으신가요?

감사합니다.

from functools import cmp_to_key
class GFG: 
    def __init__(self,graph): 
          
        # residual graph 
        self.graph = graph  
        self.ppl = len(graph) 
        self.jobs = len(graph[0]) 
  
    # A DFS based recursive function 
    # that returns true if a matching  
    # for vertex u is possible 
    def bpm(self, u, matchR, seen): 
  
        # Try every job one by one 
        for v in range(self.jobs): 
  
            # If applicant u is interested  
            # in job v and v is not seen 
            if self.graph[u][v] and seen[v] == False: 
                  
                # Mark v as visited 
                seen[v] = True 
  
                '''If job 'v' is not assigned to 
                   an applicant OR previously assigned  
                   applicant for job v (which is matchR[v])  
                   has an alternate job available.  
                   Since v is marked as visited in the  
                   above line, matchR[v]  in the following 
                   recursive call will not get job 'v' again'''
                if matchR[v] == -1 or self.bpm(matchR[v],  
                                               matchR, seen): 
                    matchR[v] = u 
                    return True
        return False
  
    # Returns maximum number of matching  
    def maxBPM(self): 
        '''An array to keep track of the  
           applicants assigned to jobs.  
           The value of matchR[i] is the  
           applicant number assigned to job i,  
           the value -1 indicates nobody is assigned.'''
        matchR = [-1] * self.jobs 
          
        # Count of jobs assigned to applicants 
        result = 0 
        for i in range(self.ppl): 
              
            # Mark all jobs as not seen for next applicant. 
            seen = [False] * self.jobs 
              
            # Find if the applicant 'u' can get a job 
            if self.bpm(i, matchR, seen): 
                result += 1
        return result 
  
  
n,m,k=map(int,input().split()) 
L=[[0]*(m) for i in range(n+k)]
worklist=[]
for i in range(n):
    M=list(map(int,input().split()))[1:]
    worklist.append(M)
def cmp(a,b):return (a>b)-(a<b)
def mycmp(L1, L2):
    return cmp(-len(L1),-len(L2))
worklist.sort(key=cmp_to_key(mycmp))
worklist1=worklist[:k]
for i in range(n+k):
    if i<k:
        for j in worklist1[i]:L[i][j-1]+=1
    else:
        for j in worklist[i-k]:L[i][j-1]+=1
g=GFG(L)
print(g.maxBPM())

exqt 3년 전 1

위 케이스에서 답이 6인데 5를 출력하시는 듯 합니다.

runnie0427 3년 전 0

감사합니다. 플로우로 다시 짜봐야겠네요.

bgoodsamari 3년 전 0

@runnie0427

선생님 해결하셨나요..?

같은이유로 틀렸는데.. 2가지일을 하는 직원을 어떻게 결정할지 모르겠네요..

runnie0427 3년 전 0

@bgoodsamari 네트워크 플로우 문제로 생각해서 sink랑 source 잘 만들어서 그래프로 변형해서 풀 면 될 거 같다고 생각하고 있기는 한데... 저도 이 이후로 손은 못대고 있네요 ㅠ 죄송합니다.

exqt 3년 전 3

sink --(cap:1)--> 직원1
ㄴ--(cap:1)-----> 직원2
ㄴ--(cap:K)-->추가노드--(cap:1)--> 직원1
              ㄴ-------(cap:1)--> 직원2

저는 이렇게 풀었습니다.

jyon 3년 전 0

저도 96%에서 막혔었는데요. 작은 힌트를 드리자면 열혈강호 2의 답을 이용해서 O(V+E)시간에 답을 구할 수 있습니다.

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

문제

문제

출처

ICPC

96%틀렸습니다 질문드립니다

runnie0427 3년 전 0

exqt 3년 전 1

runnie0427 3년 전 0

bgoodsamari 3년 전 0

runnie0427 3년 전 0

exqt 3년 전 3

jyon 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말