解题报告 『飞行员配对方案问题（网络最大流）』

#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for (register int i = a; i <= b; i++)

const int inf = 0x3f3f3f3f, maxn = 1e5 + 5;

int n, m, S, T, num_edge = 1, ans = 0;
int cur[maxn], dep[maxn], head[maxn];

queue<int> q;

struct node{
    int to, nxt, dis;
}edge[maxn];

void origin(){memset(head, -1, sizeof(head));}

int read()
{
    int x = 0, flag = 0;
    char ch = ‘ ‘;
    while (ch != ‘-‘ && (ch < ‘0‘ || ch > ‘9‘)) ch = getchar();
    if (ch == ‘-‘) 
    {
        flag = 1;
        ch = getchar();
    }
    while (ch >= ‘0‘ && ch <= ‘9‘)
    {
        x = x * 10 + ch - ‘0‘;
        ch = getchar();
    }
    return flag ? -x : x;
}

void addedge(int from, int to, int dis)
{
    edge[++num_edge].nxt = head[from];
    edge[num_edge].to = to;
    edge[num_edge].dis = dis;
    head[from] = num_edge;
}

int bfs()
{
    memset(dep, 0, sizeof(dep));
    while (!q.empty()) q.pop();
    rep(i, 0, n + 1) cur[i] = head[i];
    dep[S] = 1;
    q.push(S);
    while (!q.empty())
    {
        int u = q.front();
        q.pop();
        for (int i = head[u]; ~i; i = edge[i].nxt)
        {
            int v = edge[i].to;
            if (!dep[v] && edge[i].dis)
            {
                dep[v] = dep[u] + 1;
                q.push(v);
            }
        }
    }
    if (dep[T]) return 1;
    return 0;
}

int dfs(int u, int flow)
{
    if (u == T || !flow) return flow;
    int d, used = 0;
    for (int i = cur[u]; ~i; i = edge[i].nxt)
    {
        cur[u] = i;
        int v = edge[i].to;
        if (dep[v] == dep[u] + 1 && (d = dfs(v, min(edge[i].dis, flow))))
        {
            used += d;
            flow -= d;
            edge[i].dis -= d;
            edge[i ^ 1].dis += d;
            if (!flow) break;
        }
    }
    if (!used) dep[u] = -2;
    return used;
}

int dinic() 
{
    int ans = 0;
    while (bfs()) ans += dfs(S, inf);
    return ans;
}

void write(int x)
{
    if (x < 0)
    {
        putchar(‘-‘);
        x = -x;
    }
    if (x > 9) write(x / 10);
    putchar(x % 10 + ‘0‘);
}

int main()
{
    origin();
    m = read(), n = read();
    S = 0, T = n + 1;
    while (1)
    {
        int u, v;
        u = read(), v = read();
        if (u == -1 && v == -1) break;
        addedge(u, v, inf);
        addedge(v, u, 0);
    }
    rep(i, 1, m)
    {
        addedge(S, i, 1);
        addedge(i, S, 0);
    }
    rep(i, m + 1, n)
    {
        addedge(i, T, 1);
        addedge(T, i, 0);
    }
    ans = dinic();
    if (!ans)
    {
        printf("No Solution!");
        return 0;
    }
    write(ans);
    printf("\n");
    for (int i = 2; i <= num_edge; i += 2)
    {
        if (edge[i].to != S && edge[i ^ 1].to != S)
        if (edge[i].to != T && edge[i ^ 1].to != T)
        if (edge[i ^ 1].dis)
        {
            write(edge[i ^ 1].to);
            printf(" ");
            write(edge[i].to);
            printf("\n");
        }
    }
    return 0;
}