[BOJ] 11377 열혈강호 3

이분 매칭이 변형된 형태로 나는 에드몬드-카프 알고리즘을 사용해서 풀었다.

k명은 일을 하나씩 더 할 수 있다는 조건이 있기 때문에, source를 bridge 역할을 하는 s1과 s2에 연결한 다음 각각의 용량을 n과 k로 해주었다. 따라서 s1이 모든 사람이 하는 하나의 일, s2가 k명이 할 수 있는 추가 작업을 뜻하게 된다. 그리고 s1과 s2를 모두 사람을 표현하는 정점에 용량 1로 이어주고, 마찬가지로 사람과 일 사이에도 문제에서 주어지는 대로 용량 1인 간선을 연결해주었다. 마지막으로 일과 sink에도 용량을 1로 하여 이어주었다. 이렇게 네트워크 모델링을 하면 성공적으로 AC를 받을 수 있다. 네트워크 플로우 넘 어렵다 ㅠㅠ

#include <bits/stdc++.h>
 
using namespace std;
typedef vector<int> vi;
 
const int INF=987654321;
const int MAX_N=2010;
const int source=2001,s1=2002,s2=2003,sink=2004;
 
vector<vi> adj(MAX_N,vi());
int f[MAX_N][MAX_N],c[MAX_N][MAX_N];
 
void add_edge(int here, int there, int capacity)
{
    adj[here].push_back(there);
    adj[there].push_back(here);
    c[here][there]=capacity;
}
 
int main()
{
    int n,m,k;
    scanf("%d %d %d",&n,&m,&k);
 
    add_edge(source,s1,n);
    add_edge(source,s2,k);
 
    for(int i=1;i<=n;i++)
    {
        int t;
        scanf("%d",&t);
        add_edge(s1,i,1);
        add_edge(s2,i,1);
        for(int j=0;j<t;j++)
        {
            int work;
            scanf("%d",&work);
            add_edge(i,work+n,1);
        }
    }
    for(int i=1;i<=m;i++)
        add_edge(i+n,sink,1);
 
    int total=0;
    while(true)
    {
        vi prev(MAX_N,-1);
        queue<int> Q;
        Q.push(source);
        while(!Q.empty() && prev[sink]==-1)
        {
            int here=Q.front(); Q.pop();
            for(int i=0;i<adj[here].size();i++)
            {
                int there=adj[here][i];
                if(c[here][there]-f[here][there]<=0 || prev[there]!=-1) continue;
                Q.push(there);
                prev[there]=here;
                if(there==sink) break;
            }
        }
        if(prev[sink]==-1) break;
 
        int flow=INF;
        for(int here=sink;here!=source;here=prev[here])
            flow=min(flow,c[prev[here]][here]-f[prev[here]][here]);
        for(int here=sink;here!=source;here=prev[here])
        {
            f[prev[here]][here]+=flow;
            f[here][prev[here]]-=flow;
        }
        total+=flow;
    }
    printf("%d",total);
    return 0;
}