[网络流24题] 搭配飞行员

【问题描述】#

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

如图，假设有10个驾驶员，如图中的V1，V2，…，V10就代表达10个驾驶员,其中V1，V2，V3，V4，V5是正驾驶员,V6，V7，V8，V9，V10是副驾驶员。如果一个正驾驶员和一个副驾驶员可以同机飞行，就在代表他们两个之间连一条线,两个人不能同机飞行，就不连。例如V1和V7可以同机飞行，而V1和V8就不行。请搭配飞行员，使出航的飞机最多。注意:因为驾驶工作分工严格,两个正驾驶员或两个副驾驶员都不能同机飞行.

【输入格式】#

输入文件有若干行第一行，两个整数n与n1，表示共有n个飞行员(2<=n<=100),其中有n1名飞行员是正驾驶员. 下面有若干行,每行有2个数字a,b。表示正驾驶员a和副驾驶员b可以同机飞行。注:正驾驶员的编号在前,即正驾驶员的编号小于副驾驶员的编号.

【输出格式】#

输出文件有一行第一行，1个整数，表示最大起飞的飞机数。

【输入输出样例】#

输入文件名： flyer.in#

10 5
1 7
2 6
2 10
3 7
4 8
5 9

输出文件名：flyer.out#

题解#

二分图直接建图

1
#include <cstdio>
2
#include <queue>
3
#include <cstring>
4
using namespace std;
5
const int INF = 0x3f3f3f3f;
6
class Dinic
7
{
8
  public:
9
    struct edge
10
    {
11
        int END, next, cap;
12
    } v[1005];
13
    int first[105], p;
14
    Dinic()
15
    {
16
        memset(first, -1, sizeof(first));
17
    }
18
    void add(int a, int b, int c)
19
    {
20
        v[p].END = b, v[p].next = first[a], v[p].cap = c, first[a] = p++;
21
        v[p].END = a, v[p].next = first[b], v[p].cap = 0, first[b] = p++;
22
    }
23
    int dis[105];
24
    bool vis[10005];
25
    bool BFS(int S, int E)
26
    {
27
        memset(vis, 0, sizeof(vis));
28
        memset(dis, -1, sizeof(dis));
29
        queue<int> Q;
30
        Q.push(S);
31
        dis[S] = 0;
32
        vis[S] = 1;
33
        while (!Q.empty())
34
        {
35
            int u = Q.front();
36
            Q.pop();
37
            for (int i = first[u]; i != -1; i = v[i].next)
38
            {
39
                if (!vis[v[i].END] && v[i].cap > 0)
40
                {
41
                    vis[v[i].END] = 1;
42
                    dis[v[i].END] = dis[u] + 1;
43
                    if (v[i].END == E)
44
                        return 1;
45
                    Q.push(v[i].END);
46
                }
47
            }
48
        }
49
        return 0;
50
    }
51
    int DFS(int S, int E, int a)
52
    {
53
        if (S == E || a == 0)
54
            return a;
55
        int flow = 0, f;
56
        for (int i = first[S]; i != -1; i = v[i].next)
57
        {
58
            if (dis[v[i].END] == dis[S] + 1 && (f = DFS(v[i].END, E, min(a, v[i].cap)) > 0))
59
            {
60
                v[i].cap -= f;
61
                v[i ^ 1].cap += f;
62
                a -= f;
63
                flow += f;
64
                if (f == 0)
65
                    break;
66
            }
67
        }
68
        if (!flow)
69
            dis[S] = -1;
70
        return flow;
71
    }
72
    int dinic(int S, int E)
73
    {
74
        int ans = 0;
75
        while (BFS(S, E))
76
        {
77
            ans += DFS(S, E, INF);
78
        }
79
        return ans;
80
    }
81
} dinic;
82

83
int main(int argc, char const *argv[])
84
{
85
    freopen("flyer.in","r",stdin);
86
    freopen("flyer.out","w",stdout);
87
    int n, n1, a, b;
88
    scanf("%d%d", &n, &n1);
89
    while (scanf("%d%d", &a, &b) != EOF)
90
        dinic.add(a, b, 1);
91
    int S = 0, T = n + 1;
92
    for (int i = 1; i <= n1; i++)
93
    {
94
        dinic.add(S, i, 1);
95
    }
96
    for (int i = n1 + 1; i <= n; i++)
97
    {
98
        dinic.add(i, T, 1);
99
    }
100
    printf("%d\n", dinic.dinic(S, T));
101
    return 0;
102
}