搭配飞行员（网络流）

搭配飞行员
飞行大队有若干个来自各地的驾驶员，专门驾驶一种型号的飞机，这种飞机每架有两个驾驶员，需一个正驾驶员和一个副驾驶员。由于种种原因，例如相互配合的问题，有些驾驶员不能在同一架飞机上飞行，问如何搭配驾驶员才能使出航的飞机最多。

因为驾驶工作分工严格,两个正驾驶员或两个副驾驶员都不能同机飞行。

输入格式:
第一行，两个整数 n 与 m，表示共有 n 个飞行员，其中有 m 名飞行员是正驾驶员。下面有若干行，每行有 2 个数字a,b。表示正驾驶员 a 和副驾驶员 b 可以同机飞行。

注：正驾驶员的编号在前，即正驾驶员的编号小于副驾驶员的编号。

数据保证有 2≤n≤100

输出格式:
仅一行一个整数，表示最大起飞的飞机数。

输入样例:
在这里给出一组输入。例如：

输出样例:
在这里给出相应的输出。例如：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 1e5+10;
const int inf = 0x3f3f3f3f;
int n,m,s,t,tol,head[maxn],dep[maxn];
struct Edge
{
    int v,w,nxt;
}E[maxn];
void add_edge(int u,int v,int w)
{
    E[tol] = Edge{v,w,head[u]};
    head[u] = tol++;
}
bool Bfs()
{
    memset(dep,0, sizeof(dep));
    queue<int>q;
    while(!q.empty())
        q.pop();
    q.push(s);
    dep[s] = 1;
    while(!q.empty())
    {
        int u = q.front();
        q.pop();
        for(int i = head[u];i != -1;i = E[i].nxt)
        {
            if(E[i].w && !dep[E[i].v])
            {
                dep[E[i].v] = dep[u] + 1;
                q.push(E[i].v);
                if(E[i].v == t)
                    return true;
            }
        }
    }
    return false;
}
int Dfs(int u,int f)
{
    if(u == t)
        return f;
    int used = 0,d = 0;
    for(int i = head[u];i != -1;i = E[i].nxt)
    {
        if(dep[u] == dep[E[i].v] - 1 && E[i].w)
        {
            if((d = Dfs(E[i].v,min(f - used,E[i].w))))
            {
                used += d;
                E[i].w -= d;
                E[i^1].w += d;
            }
        }
    }
    if(!used)
        dep[u] = 0;
    return used;
}
int Dinic()
{
    int max_flow = 0,d;
    while(Bfs())
    {
        while((d = Dfs(s,inf)))
            max_flow += d;
    }
    return max_flow;
}
signed main(){
    //freopen("in","r",stdin);
    ios::sync_with_stdio(false);
    cin.tie(0);
    memset(head,-1, sizeof(head));
    int a,b;
    s = 110,t = 111;
    cin >> n >> m;
    while(cin >> a >> b){
        add_edge(a,b,1);
        add_edge(b,a,0);
    }
    for(int i = 1;i <= n; i++){
        if(i <= m){
            add_edge(s,i,1);
            add_edge(i,s,0);
            continue;
        }
        else{
            add_edge(i,t,1);
            add_edge(t,i,0);
        }
    }
    cout << Dinic()  << endl;
    return 0;
}

View Code