acmicpc.net 11375(이분 매칭), 11376(이분 매칭), 11377(이분 매칭)

https://www.acmicpc.net/problem/11375

기본적인 이분 매칭

#include <cstdio>
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

const int MAX_N = 1001;
const int MAX_M = 1001;

int n, m;
bool adj[MAX_N][MAX_M];
vector<int> aMatch, bMatch;
vector<bool> visited;

bool dfs(int a) {
  if(visited[a]) return false;
  visited[a] = true;
  for(int b = 0; b < m; ++b)
    if(adj[a][b])
      if(bMatch[b] == -1 || dfs(bMatch[b])) {
        aMatch[a] = b;
        bMatch[b] = a;
        return true;
      }
  return false;
}

int bipartiteMatch() {
  aMatch = vector<int>(n, -1);
  bMatch = vector<int>(m, -1);

  int size = 0;
  for(int start = 0; start < n; ++start) {
    visited = vector<bool>(n, false);
    if(dfs(start))
      ++size;
  }
  return size;
}

int main() {
	cin>>n>>m;
	for(int i=0;i<n;i++)
	{
		int work;
		cin>>work;
		for(int j=0;j<work;j++)
		{
			int num;
			cin>>num;
			adj[i][num-1] = true;
		}
	}
	cout<<bipartiteMatch()<<endl;
}

https://www.acmicpc.net/problem/11376

한사람이 일을 두개 할수 있다. 두개 고르면 된다. 함수 부분만 바꿔준다.

int bipartiteMatch() {
	aMatch = vector<int>(n, -1);
	bMatch = vector<int>(m, -1);

	int size = 0;
	for(int start = 0; start < n; ++start) {
		for(int i=0;i<2;i++)
		{
			visited = vector<bool>(n, false);
			if(dfs(start))
				++size;
		}
	}
	return size;
}

https://www.acmicpc.net/problem/11377

k명의 사람만 2개의 일을 할수 있다. k명을 어떻게 고를 수 있을까? (할수있는 일의 수, 사람) 형태로

저장해놓은 후 할수있는 일의 수로 내림차순 정렬한다. 그러면 할수있는 일의 수가 가장 많은 사람부터

위에 쌓이게되는데 이 정렬된 상태로 처음부터 k명을 고르면 된다.

#include <cstdio>
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <functional>
using namespace std;
 
const int MAX_N = 2001;
const int MAX_M = 1001;
 
int n, m, k;
bool adj[MAX_N][MAX_M];
vector<int> aMatch, bMatch;
vector<bool> visited;
vector<pair<int, int > > work_quantity;

bool dfs(int a) {
    if(visited[a]) return false;
    visited[a] = true;
    for(int b = 0; b < m; ++b)
        if(adj[a][b])
            if(bMatch[b] == -1 || dfs(bMatch[b])) {
                aMatch[a] = b;
                bMatch[b] = a;
                return true;
            }
    return false;
}
 
int bipartiteMatch() {
    aMatch = vector<int>(n, -1);
    bMatch = vector<int>(m, -1);
 
    int size = 0;
    for(int start = 0; start < n; ++start) { //여기 좀 바뀌었다.
		visited = vector<bool>(n, false);
		if(dfs(work_quantity[start].second))
            ++size;
        if(start < k)
		{
            visited = vector<bool>(n, false);
			if(dfs(work_quantity[start].second))
                ++size;
		}
    }
    return size;
}

bool reverse(pair<int ,int > a, pair<int, int > b) { return a.first > b.first; }

int main() {
    cin>>n>>m>>k;
    for(int i=0;i<n;i++)
    {
        int work;
        cin>>work;
		work_quantity.push_back(make_pair(work,i)); //(할수있는 일의수, 사람)
        for(int j=0;j<work;j++)
        {
            int num;
            cin>>num;
            adj[i][num-1] = true;
        }
    }
	sort(work_quantity.begin(), work_quantity.end(), greater<pair<int ,int > >()); //할수있는 일의 수로 정렬
	//for(int i=0;i<work_quantity.size();i++)
	//	cout<<i<<" = "<<work_quantity[i].first<<" "<<work_quantity[i].second<<endl;
    cout<<bipartiteMatch()<<endl;
}