[백준]11377 열혈강호 3,11378 열혈강호 4
문제
강호네 회사에는 직원이 N명이 있고, 해야할 일이 M개가 있다. 직원은 1번부터 N번까지 번호가 매겨져 있고, 일은 1번부터 M번까지 번호가 매겨져 있다.
각 직원은 한 개의 일만 할 수 있고, 각각의 일을 담당하는 사람은 1명이어야 한다. 단, N명 중에서 K명은 일을 최대 2개할 수 있다.
각각의 직원이 할 수 있는 일의 목록이 주어졌을 때, M개의 일 중에서 최대 몇 개를 할 수 있는지 구하는 프로그램을 작성하시오.
입력
첫째 줄에 직원의 수 N과 일의 개수 M, 일을 2개할 수 있는 직원의 수 K가 주어진다. (1 ≤ N, M ≤ 1,000, 1 ≤ K ≤ N)
둘째 줄부터 N개의 줄의 i번째 줄에는 i번 직원이 할 수 있는 일의 개수와 할 수 있는 일의 번호가 주어진다.
출력
첫째 줄에 강호네 회사에서 할 수 있는 일의 개수를 출력한다.
열혈강호 2와 다른점은
N명중 K명만 일을 최대 2개 할 수 있다는 점입니다
따라서 1~N명까지 일을 한번씩 시키고,
다시한번 1~N까지 일을 하나 더 시킬텐데,그 인원이 K명이 될 때까지 하면 됩니다.
K명이 다 안채워지면 더이상 일을 더 시킬 수 없다는 의미입니다.
#include<bits/stdc++.h>
using namespace std;
int N, M, K, v[1001], work[1001], num[1001], ans = 0;
vector<int>adj[1001];
bool dfs(int k) {
for (auto r : adj[k]) {
if (v[r])continue;
v[r] = 1;
if (!work[r] || dfs(work[r])) {
work[r] = k;
return true;
}
}
return false;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> N >> M >> K;
int n, a;
for (int i = 1; i <= N; i++) {
cin >> n;
while (n--) {
cin >> a;
adj[i].push_back(a);
}
}
int cnt = 0;
for (int i = 1; i <= N; i++) {
memset(v, 0, sizeof(v));
if (dfs(i))cnt++;
}
for (int i = 1; i <= N; i++) {
memset(v, 0, sizeof(v));
if (dfs(i)) {
cnt++;
K--;
}
if (K == 0)break;
}
cout << cnt;
}
문제
강호네 회사에는 직원이 N명이 있고, 해야할 일이 M개가 있다. 직원은 1번부터 N번까지 번호가 매겨져 있고, 일은 1번부터 M번까지 번호가 매겨져 있다.
각 직원은 한 개의 일만 할 수 있고, 각각의 일을 담당하는 사람은 1명이어야 한다. 여기서 지난달에 벌점을 X점 받은 사람은 일을 최대 X+1개까지 할 수 있다.
예를 들어, 직원이 3명이고, 지난달에 1번 직원 민호가 벌점을 2점, 2번 직원 재필이가 벌점을 1점, 3번 직원 주현이가 벌점을 0점 받았다면, 1번 직원 민호는 일을 최대 3개, 2번 직원 재필이는 최대 2개, 3번 직원 주현이는 최대 1개까지 할 수 있다.
각 직원은 자신이 지난달에 받은 벌점을 알지 못하고, 직원이 받은 벌점의 합 K만을 알고 있다. 강호는 이런 사실을 이용해서 벌점을 적절히 나눠서 최대한 일을 많이 할 수 있게 하려고 한다.
예를 들어, 1번 직원이 1, 2, 3, 4, 5를 할 수 있고, 2, 3, 4번 직원이 1을 할 수 있고, 5번 직원이 1, 5를 할 수 있는 경우를 생각해보자.
지난 달에 전직원이 받은 벌점의 합 K가 0이라면, 할 수 있는 일의 최대 개수는 3개이다. 1번 직원이 2를 하고, 2번 직원이 1을, 5번 직원이 5를 하면 된다.
벌점의 합 K가 2인 경우에, 1번 직원이 1점, 5번 직원이 1점을 받았다고 하면, 일을 최대 4개 할 수 있다. 1번 직원과 5번직원은 이제 일을 2개까지 할 수 있다. 1번 직원이 2와 3을, 5번 직원이 1과 5를 하면 총 4개의 일을 할 수 있다. 하지만, 강호가 벌점을 조작해 1번 직원이 2점을 받았다고 하면, 일은 최대 5개 할 수 있게 된다. 1번 직원은 일을 3개까지 할 수 있다. 따라서, 1번 직원이 2, 3, 4를 하고, 2번 직원이 1을, 5번 직원이 5를 하면 5개를 모두 할 수 있게 된다.
벌점의 합 K가 3인 경우에는, 1번 직원에게 벌점을 모두 몰아주면 일을 5개 할 수 있다. 1번 직원은 벌점이 3점이기 때문에, 일을 총 4개까지 할 수 있다. 따라서, 1, 2, 3, 4를 모두 1번직원이 하고, 5번 직원이 5를 하면 총 5가지 일을 할 수 있게 된다.
각각의 직원이 할 수 있는 일의 목록과 지난달 받은 벌점의 합 K가 주어졌을 때, M개의 일 중에서 최대 몇 개를 할 수 있는지 구하는 프로그램을 작성하시오.
입력
첫째 줄에 직원의 수 N과 일의 개수 M, 지난달에 받은 벌점의 합 K가 주어진다. (1 ≤ N, M ≤ 1,000, 1 ≤ K ≤ N)
둘째 줄부터 N개의 줄의 i번째 줄에는 i번 직원이 할 수 있는 일의 개수와 할 수 있는 일의 번호가 주어진다.
출력
첫째 줄에 강호네 회사에서 할 수 있는 일의 개수를 출력한다.
이번에는 K개의 벌점을 모든 사람들에게 나누어 주어야합니다.
일단 모두 한번씩 일을 시켜보고,
1번사람부터 N번사람까지 일을 최대한 할 수있을때까지 시켜봅니다.
K개의 벌점을 다 채우거나, 일을 더이상 못하면 끝납니다.
#include<bits/stdc++.h>
using namespace std;
int N, M, K, v[1001], work[1001];
vector<int>adj[1001];
bool dfs(int k) {
for (auto r : adj[k]) {
if (v[r])continue;
v[r] = 1;
if (!work[r] || dfs(work[r])) {
work[r] = k;
return true;
}
}
return false;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> N >> M >> K;
int n, x;
for (int i = 1; i <= N; i++) {
cin >> n;
while (n--) {
cin >> x;
adj[i].push_back(x);
}
}
int cnt = 0;
for (int i = 1; i <= N; i++) {//벌점이 0이어도 일은 하나 해야합니다.
memset(v, 0, sizeof(v));
if (dfs(i))cnt++;
}
for (int i = 1; i <= N; i++) { //K벌점을 모두 채울때까지 일을 최대한 시켜봅니다.
while (dfs(i)) {
K--;
cnt++;
if (K == 0) {
cout << cnt;
return 0;
}
}
}
cout << cnt;
}