[Cogs14] [网络流24题#1] 飞行员分配方案 [网络流，最大流，二分图匹配]

经典二分图匹配，可以用匈牙利算法，也可以用最大流

代码如下（Dinic）：

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cmath>

#include <ctime>

#include <algorithm>

#include <queue>

using namespace std;

template<const int _n>

struct Edge

{

    struct Edge_base { int    to,next,w; }e[_n]; int    p[_n],cnt;

    void    insert(const int x,const int y,const int z)

    { e[++cnt].to=y; e[cnt].next=p[x]; e[cnt].w=z; p[x]=cnt; return ; }

    int    start(const int    x) { return p[x]; }

    void    clear() { cnt=;memset(p,,sizeof(p)); }

    Edge_base&    operator[](const int x) { return e[x]; }

};

int    n,m,flow,SSS,TTT;

int    level[],From[],From_e[];

Edge<>    e;

bool    Bfs(const int S)

{

    int    i,t;

    queue<int>    Q;

    memset(level,,sizeof(level));

    memset(From,,sizeof(From));

    level[S]=;

    Q.push(S);

    while(!Q.empty())

    {

        t=Q.front(),Q.pop();

        for(i=e.start(t);i;i=e[i].next)

        {

            if(!level[e[i].to] && e[i].w)

            {

                level[e[i].to]=level[t]+;

                Q.push(e[i].to);

                From[e[i].to]=t;

                From_e[e[i].to]=i;

                if(e[i].to==TTT)goto End;

            }

        }

    }

End:

    if(!level[TTT])return false;

    flow++;

    for(i=TTT;i!=SSS;i=From[i])e[From_e[i]].w--,e[From_e[i]^].w++;

    return true;

}

int    Dinic()

{

    while(Bfs(SSS));

    return flow;

}

int main()

{

    freopen("flyer.in","r",stdin);

    freopen("flyer.out","w",stdout);

    int    i,x,y;

    scanf("%d%d",&m,&n);

    m=m-n;

    while(scanf("%d%d",&x,&y)==)

    {

        if(x>y)swap(x,y);

        e.insert(x,y,);

        e.insert(y,x,);

    }

    SSS=n+m+,TTT=n+m+;

    for(i=;i<=n;++i)

    {

        e.insert(SSS,i,);

        e.insert(i,SSS,);

    }

    for(i=n+;i<=m+n;++i)

    {

        e.insert(i,TTT,);

        e.insert(TTT,i,);

    }

    printf("%d\n",Dinic());

    return ;

}

匈牙利代码：http://www.cnblogs.com/Ngshily/p/4988909.html