Power Oj-1736:飞行员配对方案问题(网络流（最大流———Dinic算法）)

图论 AAA不懂

Dinic算法简介
Dinic算法是网络流最大流的优化算法之一，每一步对原图进行分层，然后用DFS求增广路。时间复杂度是O(n^2*m)。

（From洋哥的模板先放这里，对dinic还不懂的我）
#include<bits/stdc++.h>
using namespace std;
const int maxn = 100;
const int maxm = 4000;
struct EDGE
{
    int to, next, flow;
    EDGE(int to = 0, int next = 0, int flow = 0): to(to), next(next), flow(flow) {}
} edge[maxm];
int head[maxn], edgecnt, maxNodeNum;
void init()
{
    memset(head, -1, sizeof(head));
    edgecnt = 0;
    maxNodeNum = 0;
}
void AddEdge(int s, int t, int c)
{
    edge[edgecnt] = EDGE(t, head[s], c);
    head[s] = edgecnt++;
    edge[edgecnt] = EDGE(s, head[t], 0);
    head[t] = edgecnt++;
    maxNodeNum = max(maxNodeNum, max(s, t));
}
int layer[maxn];
int p[maxn];
bool GetLayer(int st, int en)
{
    memset(layer, 0, sizeof(int) * (maxNodeNum + 1));
    layer[st] = 1;
    queue<int>q;
    q.push(st);
    while(!q.empty())
    {
        int u = q.front();
        q.pop();
        for(int i = head[u]; ~i; i = edge[i].next)
        {
            if(edge[i].flow == 0)
                continue;
            int v = edge[i].to;
            if(layer[v])
                continue;
            layer[v] = layer[u] + 1;
            q.push(v);
        }
    }
    return layer[en];
}
int dfsFlow(int u, int en, int f)
{
    int ret = 0;
    if(u == en)
        return f;
    if(layer[u] >= layer[en])
        return 0;
    for(; ~p[u]; p[u] = edge[p[u]].next)
    {
        if(edge[p[u]].flow == 0)
            continue;
        int v = edge[p[u]].to;
        if(layer[v] != layer[u] + 1)
            continue;
        int temp = dfsFlow(v, en, min(f, edge[p[u]].flow));
        ret += temp;
        f -= temp;
        edge[p[u]].flow -= temp;
        edge[p[u] ^ 1].flow += temp;
        if(f == 0)
            break;
    }
    return ret;
}
int dinic(int st, int en)
{
    int ans = 0;
    while(GetLayer(st, en))
    {
        memcpy(p, head, sizeof(int) * (maxNodeNum + 1));
        ans += dfsFlow(st, en, INT_MAX);
    }
    return ans;
}
int main()
{
    init();
    int n, m;
    scanf("%d %d", &n, &m);
    for(int i = 1; i <= n; i++)
        AddEdge(0, i, 1);
    for(int i = n + 1; i <=  m; i++)
        AddEdge(i,  m + 1, 1);
    int u, v;
    while(scanf("%d %d", &u, &v), u != -1 && v != -1)
    {
        AddEdge(u, v, 1);
    }
    int ans = dinic(0,  m + 1);
    if(ans == 0)
    {
        printf("No Solution!");
        return 0;
    }
    printf("%d\n", ans);
    for(int i = 1; i <= n; i++)
        for(int j = head[i]; ~j; j = edge[j].next)
            if(edge[j].to > n && edge[j].flow == 0)
            {
                printf("%d %d\n", i, edge[j].to);
                break;
            }
    return 0;
}