글 읽기 - 이렇게 풀면 틀리는 이유가 멀까요?

upple1 5년 전 0

각 사람당 k의 한도 내에서 한명씩 최대로 매칭할 수 있는대로 매칭하면서 넘어가는 식으로 풀었는데 틀리더라고요.

그래서 우선 하나씩 전부 연결한 뒤 k를 채우는 방식으로 푸니깐 맞네요.

아무리 생각해도 첫번 쨰 방식이 틀리는 이유를 모르겠어요...

#include <bits/stdc++.h>
using namespace std;

int n, m, k;
vector<int> adj[1001];
int p[1001];
bool v[1001];

bool dfs(int x)
{
    v[x]=1;
    for(int i : adj[x])
    {
        if(!p[i] || (!v[p[i]] && dfs(p[i])))
        {
            p[i]=x;
            return true;
        }
    }

    return false;
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin>>n>>m>>k;
    for(int i=1; i<=n; i++)
    {
        int s;
        cin>>s;
        adj[i].resize(s);
        for(int &j : adj[i])
            cin>>j;
    }

    int match=0;
    /* 맞는 풀이
    for(int i=1; i<=n; i++)  //우선 하나씩 매칭 시도
    {
        memset(v, 0, n+1);
        if(dfs(i)) match++;
    }

    for(int i=1; i<=n && match<m; i++)
    {
        while(k)
        {
            memset(v, 0, n+1);
            if(!dfs(i)) break;

            match++;
            k--;
        }
        
    }*/
    
    /* 틀리는 풀이
    for(int i=1; i<=n; i++)
    {
        memset(v, 0, n+1);
        if(!dfs(i)) continue;
        match++;
        while(k)    // 그때그때 최대한 매칭
        {
            memset(v, 0, n+1);
            if(!dfs(i)) break;

            match++;
            k--;
        }
        
    }*/

    cout<<match;
}

choyj2012 3년 전 4

이런 경우에 반례가 되네요

모든 직원이 벌점을 안쓰고 일을 한개씩은 할 수 있는데 위에서 k를 다 써버려서 일을 한개도 할 수 없는 사람이 생기네요

/*
input
3 6 3
3 1 2 3
1 3
4 3 4 5 6

output(틀린풀이)
5

output(맞는풀이)
6
*/

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

문제

문제

출처

ICPC

이렇게 풀면 틀리는 이유가 멀까요?

upple1 5년 전 0

choyj2012 3년 전 4

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말