建立一个超级源点，将每个外籍飞行员连一条capacity为1的路，一个超级汇点，每个英国飞行员也连一条capacity为1的路，根据读入在英国飞行员和外籍飞行员连接capacity为1的路，匹配方案就是最大流，遍历每一个外籍飞行员的连接，当有流时就输出即可
#include<bits/stdc++.h>
using namespace std;
#define lowbit(x) ((x)&(-x))
typedef long long LL; const int maxm = 3e4+;
const int INF = 0x3f3f3f3f; struct edge{
int u, v, cap, flow, nex;
} edges[maxm<<]; int head[maxm<<], cur[maxm<<], cnt, level[]; void init() {
memset(head, -, sizeof(head));
} void add(int u, int v, int cap) {
edges[cnt] = edge{u, v, cap, , head[u]};
head[u] = cnt++;
} void addedge(int u, int v, int cap) {
add(u, v, cap), add(v, u, );
} void bfs(int s) {
memset(level, -, sizeof(level));
queue<int> q;
level[s] = ;
q.push(s);
while(!q.empty()) {
int u = q.front();
q.pop();
for(int i = head[u]; i != -; i = edges[i].nex) {
edge& now = edges[i];
if(now.cap > now.flow && level[now.v] < ) {
level[now.v] = level[u] + ;
q.push(now.v);
}
}
}
} int dfs(int u, int t, int f) {
if(u == t) return f;
for(int& i = cur[u]; i != -; i = edges[i].nex) {
edge& now = edges[i];
if(now.cap > now.flow && level[u] < level[now.v]) {
int d = dfs(now.v, t, min(f, now.cap - now.flow));
if(d > ) {
now.flow += d;
edges[i^].flow -= d;
return d;
} }
}
return ;
} int dinic(int s, int t) {
int maxflow = ;
for(;;) {
bfs(s);
if(level[t] < ) break;
memcpy(cur, head, sizeof(head));
int f;
while((f = dfs(s, t, INF)) > )
maxflow += f;
}
return maxflow;
} void run_case() {
int n, m, u, v, cap;
init();
cin >> m >> n;
for(int i = ; i <= m; ++i)
addedge(, i, );
while(cin >> u >> v && (u+v)>) {
addedge(u, v, );
}
for(int i = m+; i <= n; ++i)
addedge(i, n+, );
int maxflow = dinic(, n+);
if(maxflow == ) {
cout << "No Solution!\n";
return;
}
cout << maxflow << "\n";
for(int u = ; u <= m; ++u) {
for(int i = head[u]; i != -; i = edges[i].nex)
if(edges[i].flow) {cout << edges[i].u << " " << edges[i].v << "\n"; break;}
}
} int main() {
ios::sync_with_stdio(false), cin.tie();
run_case();
//cout.flush();
return ;
}
Dinic