1736 飞行员配对方案问题(二分图)

//https://www.oj.swust.edu.cn/problem/show/1736
//ID:Gavin
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<string>
#include<algorithm>
#include<map>
#include<queue>
#include<vector>
#include<cmath>
#include<utility>
using namespace std;
typedef long long LL;
const int N = 1008, INF = 0x3F3F3F3F , M = 100000;
#define MS(a, num) memset(a, num, sizeof(a))
#define PB(A) push_back(A)
#define FOR(i, n) for(int i = 0; i < n; i++)

int cx[N], cy[N];//匹配结果
int nx, ny;//x,y集合元素个数
bool vis[N];
//存x到y集合的有向图
struct Node{
	int to,next;
}edge[M];
int head[N],tot;

bool dfs(int u){
    for(int i = head[u]; ~i; i = edge[i].next){
        int v = edge[i].to;
        if(!vis[v]){
            vis[v] = true;
            if(cy[v] == -1 || dfs(cy[v])){
                cx[u] = v;
                cy[v] = u;
                return true;
            }
        }
    }
    return false;
}

int Hungary(){
    int ans = 0;
    memset(cx, -1, sizeof(cx));
    memset(cy, -1, sizeof(cy));
    for(int i = 1; i <= nx; i++){
        if(cx[i] == -1){
            memset(vis, 0, sizeof(vis));
            if(dfs(i)){
                ans++;
            }
        }
    }
    return ans;
}

void init(){
	memset(head, -1, sizeof(head));
	tot = 0;
}
void add(int u, int to){
	edge[tot].to=to;
	edge[tot].next=head[u];
	head[u]=tot++;
}
int main(){
	int m ,n;
	cin>>m>>n;
    init();
	nx = m, ny = n;
	int u, v;
	while(~scanf("%d %d", &u, &v)){
		if(u == -1 || v == -1){
			break;
		}
		add(u, v - m);
	}
	int ans = Hungary();
	if(ans == 0){
		printf("No Solution!
");
	}else{
		printf("%d
", ans);
		for(int i = 1;  i <= m; i++){
			if(cx[i] != -1){
				printf("%d %d
", i, cx[i] + m);
			}
		}


	}
	return 0;
}