1, 2번 정점은 여러번 지날 수 있어야 하므로 (in -> out) 간선 용량은 400(최대 경로 수) 로 지정
u - v : 양방향 간선을 두개의 단방향 간선으로 (u out -> v in, v out -> u in)
정점 모델링
코드
#include <bits/stdc++.h>
using namespace std;
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
struct Edge {
int to, c, f;
Edge* reverse;
Edge() {
to = c = f = 0;
reverse = nullptr;
}
Edge(int to_, int c_) {
f = 0;
c = c_;
to = to_;
reverse = nullptr;
}
int residual() {
return c - f;
}
};
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int N, P;
cin >> N >> P;
vector<vector<Edge*> > adj(2 * N + 1);
auto makeEdge = [&](int u, int v, int c) {
auto e1 = new Edge(v, c);
auto e2 = new Edge(u, 0);
e1 -> reverse = e2;
e2 -> reverse = e1;
adj[u].push_back(e1);
adj[v].push_back(e2);
};
for (int i = 0; i < P; ++i) {
int u, v;
cin >> u >> v;
makeEdge(2 * u, 2 * v - 1, 1);
makeEdge(2 * v, 2 * u - 1, 1);
}
for (int i = 1; i <= N; ++i) {
int c = 1;
if (i == 1 || i == 2) c = 400;
makeEdge(2 * i - 1, 2 * i, c);
}
int S = 1 * 2 - 1;
int T = 2 * 2;
int answer = 0;
while (true) {
vector<Edge*> prev(2 * N + 1, nullptr);
queue<int> q;
q.push(S);
while (q.size()) {
auto f = q.front();
q.pop();
for (auto e: adj[f]) {
if (prev[e -> to]) continue;
if (e -> residual() <= 0) continue;
q.push(e -> to);
prev[e -> to] = e;
if (e -> to == T) break;
}
if (prev[T]) break;
}
if (!prev[T]) break;
int flow = 1e9;
for (int cur = T; cur != S; cur = prev[cur] -> reverse -> to) {
flow = min(flow, prev[cur] -> residual());
}
for (int cur = T; cur != S; cur = prev[cur] -> reverse -> to) {
prev[cur] -> f += flow;
prev[cur] -> reverse -> f -= flow;
}
answer += flow;
}
cout << answer << '\n';
}
#include <bits/stdc++.h>
using namespace std;
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
struct Edge {
int to, c, f;
Edge* reverse;
Edge() {
to = 0;
c = 0;
f = 0;
reverse = nullptr;
}
int residual() {
return c - f;
}
};
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int N, M, K;
cin >> N >> M >> K;
vector<vector<Edge*> > adj(N + M + 3);
auto makeEdge = [&](int n1, int n2, int cc) {
auto e1 = new Edge();
auto e2 = new Edge();
e1 -> to = n2;
e1 -> reverse = e2;
e1 -> c = cc;
e2 -> to = n1;
e2 -> reverse = e1;
adj[n1].push_back(e1);
adj[n2].push_back(e2);
};
int S = 0, T = N + M + 1, X = N + M + 2;
makeEdge(S, X, K);
for (int i = 1; i <= N; ++i) {
int num;
cin >> num;
makeEdge(S, i, 1);
makeEdge(X, i, 1);
while (num--) {
int w;
cin >> w;
makeEdge(i, N + w, 1);
}
}
for (int i = 1; i <= M; ++i) {
makeEdge(N + i, T, 1);
}
while (true) {
vector<Edge*> prev(N + M + 3, nullptr);
queue<int> q;
q.push(S);
while (!q.empty()) {
auto f = q.front();
q.pop();
for (auto e: adj[f]) {
if (e -> residual() <= 0) continue;
if (prev[e -> to]) continue;
q.push(e -> to);
prev[e -> to] = e;
if (e -> to == T) break;
}
if (prev[T]) break;
}
if (!prev[T]) break;
int flow = 1e9;
for (auto cur = T; cur != S; cur = prev[cur] -> reverse -> to) {
flow = min(flow, prev[cur] -> residual());
}
for (auto cur = T; cur != S; cur = prev[cur] -> reverse -> to) {
prev[cur] -> f += flow;
prev[cur] -> reverse -> f -= flow;
}
}
int answer = 0;
for (auto e: adj[T]) {
answer += e -> reverse -> f;
}
cout << answer << '\n';
}
풀이2. Bipartite matching
직원당 두개의 노드를 만들고 그룹 두개로 나눠서 한그룹에서 이분매칭 후 두번째 그룹에서 K번 이하 이분매칭
코드2.
시간복잡도: $O(VE)$
#include <bits/stdc++.h>
using namespace std;
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int N, M, K;
cin >> N >> M >> K;
vector<int> A(2 * N + 1, 0), B(M + 1, 0);
vector<vector<int> > adj(2 * N + 1);
for (int i = 1; i <= N; ++i) {
int num;
cin >> num;
while (num--) {
int m;
cin >> m;
adj[2 * i - 1].push_back(m);
adj[2 * i].push_back(m);
}
}
vector<int> visited(2 * N + 1, false);
function<bool(int)> f = [&](int a) {
visited[a] = true;
for (auto b: adj[a]) {
if (!B[b] || (!visited[B[b]] && f(B[b]))) {
A[a] = b;
B[b] = a;
return true;
}
}
return false;
};
int match = 0;
for (int i = 1; i <= 2 * N; i += 2) {
if (!A[i]) {
fill(all(visited), false);
if (f(i)) ++match;
}
}
int matched2 = 0;
for (int i = 2; i <= 2 * N && matched2 < K; i += 2) {
if (!A[i]) {
fill(all(visited), false);
if (f(i)) ++matched2;
}
}
cout << match + matched2 << '\n';
}
