题目描述
题目链接:飞行员配对方案问题
思路
二分图匹配问题
建立超级源,超级汇点,跑最大流即可。
代码
#include <bits/stdc++.h>
#define fast_io \
ios::sync_with_stdio(false); \
cin.tie(0); \
cout.tie(0)
using namespace std;
using ll = long long;
using P = pair<int, int>;
const int inf = 0x3f3f3f3f;
const ll llinf = 0x3f3f3f3f3f3f3f3fll;
const int onf = 0xcfcfcfcf;
const int N = (int)1e5 + 5;
const int M = (int)1e5 + 5;
const int mod = (int)1e9 + 7;
const double esp = 1e-8;
//------------天佑AC------------------
struct Edge {
int v, w, next;
};
struct Dinic {
vector<Edge> edge;
vector<int> head;
vector<int> depth;
vector<int> cur;
Dinic(int n) {
head.assign(n + 1, -1);
}
void add_edge(int u, int v, int w) {
edge.push_back((Edge){v, w, head[u]});
head[u] = edge.size() - 1;
edge.push_back((Edge){u, 0, head[v]});
head[v] = edge.size() - 1;
}
bool bfs(int s, int t) {
depth.assign(head.size(), 0);
depth[s] = 1;
queue<int> que;
que.push(s);
while (!que.empty()) {
int u = que.front();
que.pop();
for (int i = head[u]; i != -1; i = edge[i].next) {
const Edge &e = edge[i];
if (!depth[e.v] && e.w) {
depth[e.v] = depth[u] + 1;
que.push(e.v);
}
}
}
if (depth[t] == 0)
return false;
return true;
}
int dfs(int u, int s, int t, int flow) {
if (u == t)
return flow;
for (int &i = cur[u]; i != -1; i = edge[i].next) {
Edge &e = edge[i];
if (depth[u] + 1 == depth[e.v] && e.w) {
int f = dfs(e.v, s, t, min(flow, e.w));
if (f > 0) {
e.w -= f;
edge[i ^ 1].w += f;
return f;
}
}
}
return 0;
}
int solve(int s, int t) {
int ans = 0;
while (bfs(s, t)) {
cur = head;
while (int flow = dfs(s, s, t, inf)) {
ans += flow;
}
}
return ans;
}
};
int main() {
fast_io;
int n1, n2;
cin >> n1 >> n2;
Dinic solve(n2 + 2);
int u, v;
int m = 0;
while (cin >> u >> v, u != -1 && v != -1) {
solve.add_edge(u, v, 1);
++m;
}
m <<= 1;
for (int i = 1; i <= n1; ++i)
solve.add_edge(n2 + 1, i, 1);
for (int i = n1 + 1; i <= n2; ++i)
solve.add_edge(i, n2 + 2, 1);
cout << solve.solve(n2 + 1, n2 + 2) << endl;
auto &edge = solve.edge;
for (int i = 0; i < m; i += 2) {
if (!edge[i].w) {
cout << edge[i ^ 1].v << ' ' << edge[i].v << endl;
}
}
return 0;
}