글 읽기 - 필요없다고 생각하는 부분을 지웠더니 틀렸습니다가 나옵니다 ( 전에는 맞았습니다 )

ckdtjq1121 1년 전 0

코드의 43 line ~ 49 line, 56 line ~ 57 line 부분은 ( 2개의 일할 수 있는사람 k명을 count하기 위해서 작성했던 코드)

시작 - k - 사람 간선을 추가하기 전에 작성했던 코드라서 이제는 필요없는 코드라 생각되어 지우고 제출을 했더니

틀렸습니다가 나옵니다 ( 저 코드가 있으면 맞았습니다가 나옵니다 )

저 부분이 없다면 어떤 반례에 걸리는지 알 수 있을까요?

#include <bits/stdc++.h>

using namespace std;

int n, m, k;
int vn;
const int INF = 1001;
vector<vector<int>> c, f, adj;
vector<int> parent;

int maxFlow(int src, int dst)
{
    int total_flow = 0;
    while (1)
    {
        queue<int> q;
        q.push(src);

        parent = vector<int>(vn, -1);
        parent[src] = src;

        while (!q.empty() && parent[dst] == -1)
        {
            int u = q.front();
            q.pop();
            for (int i = 0; i < adj[u].size(); i++)
            {
                int v = adj[u][i];

                if (c[u][v] - f[u][v] > 0 && parent[v] == -1)
                {
                    q.push(v);
                    parent[v] = u;
                }
            }
        }

        if (parent[dst] == -1)
            break;

        int amount = 1;

        for (int i = dst; i != src; i = parent[i])
        {
            if (parent[i] == src && f[parent[i]][i])
            {
                k--;
            }
        }

        for (int i = dst; i != src; i = parent[i])
        {
            f[parent[i]][i] += amount;
            f[i][parent[i]] -= amount;
        }
        if(k > 0)
        total_flow += amount;
    }

    return total_flow;
}

int main()
{
    cin >> n >> m >> k;

    // s 0, person 1~n, task n+1~n+m, e n+m+1, k n+m+2
    vn = n + m + 3;

    c = vector<vector<int>>(vn, vector<int>(vn, 0));
    f = c;
    adj = vector<vector<int>>(vn);

    int s = 0, e = n+m+1, kk = n+m+2;
    adj[s].push_back(kk);
    adj[kk].push_back(s);
    c[s][kk] = k;
    for(int i = 1; i <= n; i++)
    {
        adj[s].push_back(i);
        adj[i].push_back(s);

        adj[kk].push_back(i);
        adj[i].push_back(kk);

        c[s][i] = c[kk][i] = 1;
    }

    for (int i = 1; i <= n; i++)
    {
        int num;
        cin >> num;

        for (int j = 0; j < num; j++)
        {
            int task;
            cin >> task;
            task += n;

            adj[i].push_back(task);
            adj[task].push_back(i);

            c[i][task] = 1;
        }
    }

    for (int i = 1; i <= m; i++)
    {
        adj[n + i].push_back(n + m + 1);
        adj[n + m + 1].push_back(n + i);

        c[n + i][n + m + 1] = 1;
    }
    
    int ans = maxFlow(0, e);
    cout << ans << "\n";
}

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

문제

문제

출처

ICPC

필요없다고 생각하는 부분을 지웠더니 틀렸습니다가 나옵니다 ( 전에는 맞았습니다 )

ckdtjq1121 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말