매점 (JUNGOL 1117)

https://jungol.co.kr/problem/1117?cursor=MTQsNywx

---

아이디어

이분 매칭 또는 최대 유량을 구해주면 됩니다. 최대 유량을 구할 때에는 0->1, 0->2, ... 0->N을 잇는 크기 1의 간선과 N+1->N+M+1,N+2->N+M+1,...N+M->N+M+1을 잇는 크기 1의 간선, 그리고 i -> N+j를 잇는 크기 1의 간선으로 이루어진 그래프에서의 0->N+M+1의 최대 유량을 구해주면 됩니다.

---

소스코드

#include <iostream>
#include <vector>
#include <queue>
#define ll long long
using namespace std;

ll Capacity[444][444]={0},Flow[444][444]={0};
vector <ll> Graph[444];

ll MaxFlow(ll Start,ll End)
{
    ll res=0;
    while (true)
    {
        queue <ll> q;
        ll before[444]={0};
        for (ll i=1;i<=End;i++) before[i]=-1;

        q.push(Start);
        while (q.size())
        {
            ll now=q.front();
            q.pop();

            for (ll next:Graph[now])
            {
                if (before[next]!=-1) continue;
                if (Flow[now][next]==Capacity[now][next]) continue;
                before[next]=now;
                q.push(next);
            }
        }

        if (before[End]==-1) break;

        ll mn=1e18,temp=End;
        while (temp!=Start)
        {
            mn=min(mn,Capacity[before[temp]][temp]-Flow[before[temp]][temp]);
            temp=before[temp];
        }
        
        res+=mn;
        temp=End;
        while (temp!=Start)
        {
            Flow[before[temp]][temp]+=mn;
            Flow[temp][before[temp]]-=mn;
            temp=before[temp];
        }
    }

    return res;
}

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    ll N,M,K,i,x;

    cin>>N>>M;
    
    for (i=1;i<=N;i++) Graph[0].push_back(i),Graph[i].push_back(0),Capacity[0][i]=1;

    for (i=1;i<=N;i++)
    {
        cin>>K;
        for (ll j=1;j<=K;j++)
        {
            cin>>x;
            Graph[i].push_back(N+x);
            Graph[N+x].push_back(i);
            Capacity[i][N+x]=1;
        }
    }

    for (i=1;i<=M;i++) Graph[i+N].push_back(N+M+1),Graph[N+M+1].push_back(i+N),Capacity[i+N][N+M+1]=1;

    cout<<MaxFlow(0,N+M+1);
}