【题目链接】点击打开链接

【解题方法1】 容易看出，这题就是裸的最大二分匹配，所以直接上最大匹配板子就可以过了。

【AC代码1】

//
//Created by just_sort 2016/12/23
//Copyright (c) 2016 just_sort.All Rights Reserved
//

//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//#include <ext/pb_ds/hash_policy.hpp>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <sstream> //isstringstream
#include <iostream>
#include <algorithm>
using namespace std;
//using namespace __gnu_pbds;
typedef long long LL;
//typedef pair<int, LL> pp;
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPZ(i, n) for(int i = 1; i < n; i++)
#define MP(x,y) make_pair(x,y)
const int maxn = 1100;
const int maxm = 1<<12;
const int inf = 0x3f3f3f3f;
//typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>order_set;
//head

vector <int> G[110];
int n, m, link[110], used[110];

bool dfs(int u)
{
    for(int i = 0; i < (int)G[u].size(); i++){
        int v = G[u][i];
        if(!used[v]){
            used[v] = 1;
            if(link[v] == -1 || dfs(link[v])){
                link[v] = u;
                return true;
            }
        }
    }
    return false;
}

int maxmatch()
{
    int ans = 0;
    memset(link, -1, sizeof(link));
    for(int i = 1; i <= n; i++){
        memset(used, false, sizeof(used));
        if(dfs(i)) ans++;
    }
    return ans;
}

int main()
{
    while(scanf("%d%d", &n,&m) != EOF)
    {
        for(int i = 0; i < 110; i++) G[i].clear();
        int x, y;
        while(scanf("%d%d", &x,&y))
        {
            if(x == -1 && y == -1) break;
            G[x].push_back(y);
        }
        int ans = maxmatch();
        if(ans == 0){
            printf("No Solution!\n");
        }
        else{
            printf("%d\n", ans);
            for(int i = n + 1; i <= m; i++){
                if(link[i] != -1){
                    printf("%d %d\n", link[i], i);
                }
            }
        }
    }
    return 0;
}

【解题方法2】除了最大二分匹配，我们也可以把这题转化成最大流来做，将原图中的所有无向边改成有向边，方向从u到v，容量为1。增加源点s和汇点t，从s向所有的顶点属于U连一条容量为1的边，从所有的顶点v属于V向t连一条容量为1的边。 这样变形之后得到的新图中的最大s-t流的流量就是原二分图G中最大匹配的匹配数，而u,v之间的流量为正的边集合就是最大匹配。我这里用Dinic算法跑的最大流。

【AC代码2】


//
//Created by just_sort 2016/12/25
//Copyright (c) 2016 just_sort.All Rights Reserved
//

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/hash_policy.hpp>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <sstream> //isstringstream
#include <iostream>
#include <algorithm>
using namespace std;
using namespace __gnu_pbds;
typedef long long LL;
typedef pair<int, LL> pp;
#define REP1(i, a, b) for(int i = a; i < b; i++)
#define REP2(i, a, b) for(int i = a; i <= b; i++)
#define MP(x,y) make_pair(x,y)
const int maxn = 105;
const int maxm = 1<<12;
const int maxs = 1e6+7;
const int INF = 0x3f3f3f3f;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>order_set;
//head

struct edge{int from, to, cap, flow; };
vector <edge> edges;
vector <int> G[maxn]; //图的邻接表表示
int level[maxn]; //顶点到源点的距离编号
int iter[maxn]; //当前弧，在其之前的边已经没用了
bool vis[maxn];
int s, t, x, y;

void addedge(int from, int to, int cap){ //向图中增加一条从from到to的容量为cap的边
    edges.push_back((edge){from, to, cap, 0});
    edges.push_back((edge){to, from, 0, 0});
    int sz = edges.size();
    G[from].push_back(sz - 2);
    G[to].push_back(sz - 1);
}

//通过bfs计算从源点出发的距离标号

bool bfs()
{
    memset(vis, false, sizeof(vis));
    queue <int> que;
    que.push(s);
    level[s] = 0;
    vis[s] = 1;
    while(que.size())
    {
        int u = que.front(); que.pop();
        for(int i = 0; i < G[u].size(); i++){
            edge &e = edges[G[u][i]];
            if(!vis[e.to] && e.cap > e.flow){
                level[e.to] = level[u] + 1;
                vis[e.to] = 1;
                que.push(e.to);
            }
        }
    }
    return vis[t];
}

//通过DFS寻找增广路

int dfs(int u, int a)
{
    if(u == t || a == 0) return a;
    int f, flow = 0;
    for(int &i = iter[u]; i < (int) G[u].size(); i++){
        edge &e = edges[G[u][i]];
        if(level[e.to] == level[u] + 1 && (f = dfs(e.to, min(a, e.cap - e.flow))) > 0){
            e.flow += f;
            edges[G[u][i]^1].flow -= f;
            flow += f;
            a -= f;
            if(a == 0) break;
        }
    }
    return flow;
}

//求解从s到t的最大流


int max_flow(){
    int flow = 0;
    while(bfs())
    {
        memset(iter, 0, sizeof(iter));
        flow += dfs(s, INF);
    }
    return flow;
}


int main()
{
    int n, m;
    while(scanf("%d%d", &n,&m) != EOF)
    {
        for(int i = 0; i < 105; i++) G[i].clear();
        edges.clear();
        while(scanf("%d%d", &x,&y)){
            if(x == -1 && y == -1) break;
            addedge(x, y, 1);
        }
        s = 0, t = m + 1;
        for(int i = 1; i <= n; i++) addedge(s, i, 1);
        for(int i = n + 1; i <= m; i++) addedge(i, t, 1);
        int ans = max_flow();
        if(ans <= 0){
            printf("No Solution!\n");
        }
        else{
            printf("%d\n", ans);
            int sz = edges.size();
            for(int i = 0; i < sz; i += 2){
                edge &e = edges[i];
                if(e.flow == 1 && e.from != s && e.to != t){
                    printf("%d %d\n", e.from, e.to);
                }
            }
        }
    }
    return 0;
}