742 字
4 分钟
[网络流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
4
题解
二分图直接建图
#include <cstdio>#include <queue>#include <cstring>using namespace std;const int INF = 0x3f3f3f3f;class Dinic{ public: struct edge { int END, next, cap; } v[1005]; int first[105], p; Dinic() { memset(first, -1, sizeof(first)); } void add(int a, int b, int c) { v[p].END = b, v[p].next = first[a], v[p].cap = c, first[a] = p++; v[p].END = a, v[p].next = first[b], v[p].cap = 0, first[b] = p++; } int dis[105]; bool vis[10005]; bool BFS(int S, int E) { memset(vis, 0, sizeof(vis)); memset(dis, -1, sizeof(dis)); queue<int> Q; Q.push(S); dis[S] = 0; vis[S] = 1; while (!Q.empty()) { int u = Q.front(); Q.pop(); for (int i = first[u]; i != -1; i = v[i].next) { if (!vis[v[i].END] && v[i].cap > 0) { vis[v[i].END] = 1; dis[v[i].END] = dis[u] + 1; if (v[i].END == E) return 1; Q.push(v[i].END); } } } return 0; } int DFS(int S, int E, int a) { if (S == E || a == 0) return a; int flow = 0, f; for (int i = first[S]; i != -1; i = v[i].next) { if (dis[v[i].END] == dis[S] + 1 && (f = DFS(v[i].END, E, min(a, v[i].cap)) > 0)) { v[i].cap -= f; v[i ^ 1].cap += f; a -= f; flow += f; if (f == 0) break; } } if (!flow) dis[S] = -1; return flow; } int dinic(int S, int E) { int ans = 0; while (BFS(S, E)) { ans += DFS(S, E, INF); } return ans; }} dinic;
int main(int argc, char const *argv[]){ freopen("flyer.in","r",stdin); freopen("flyer.out","w",stdout); int n, n1, a, b; scanf("%d%d", &n, &n1); while (scanf("%d%d", &a, &b) != EOF) dinic.add(a, b, 1); int S = 0, T = n + 1; for (int i = 1; i <= n1; i++) { dinic.add(S, i, 1); } for (int i = n1 + 1; i <= n; i++) { dinic.add(i, T, 1); } printf("%d\n", dinic.dinic(S, T)); return 0;}