Prelude
传送到LOJ
这是一道二分图最大匹配的裸题，直接水过去就好。。。
Solution
从\(S\)向每个正驾驶员连边，从正驾驶员向可以同机飞行的副驾驶员连边，从每个副驾驶员向\(T\)连边，所有边容量均为1，网络最大流即为答案。
Code
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 |
#include <cstdio> #include <cstring> #include <queue> #include <algorithm> using namespace std; const int MAXN = 110; const int MAXM = 100000; const int INF = 0x3f3f3f3f; namespace Dinic { struct Edge { int u,v,c,f; Edge() {} Edge(int u, int v, int c, int f): u(u), v(v), c(c), f(f) {} }; int n,m,s,t; Edge edge[MAXM]; int head[MAXN],nxt[MAXM]; int dis[MAXN],cur[MAXN]; void init(int _n) { n = _n, m = 0; for(int i = 0; i < n; ++i) head[i] = -1; } void adde(int u, int v, int c) { edge[m] = Edge(u,v,c,0); nxt[m] = head[u]; head[u] = m++; edge[m] = Edge(v,u,0,0); nxt[m] = head[v]; head[v] = m++; } queue<int> q; bool bfs() { for(int i = 0; i < n; ++i) dis[i] = INF; dis[s] = 0; q.push(s); while(!q.empty()) { int u = q.front(); q.pop(); for(int i = head[u]; ~i; i = nxt[i]) { Edge &e = edge[i]; if(e.c > e.f && dis[e.v] == INF) { dis[e.v] = dis[u] + 1; q.push(e.v); } } } return dis[t] != INF; } int dfs(int u, int res) { if(u == t || !res) return res; int flow = 0, f; for(int &i = cur[u]; ~i; i = nxt[i]) { Edge &e = edge[i]; if(e.c > e.f && dis[e.v] == dis[u] + 1) { f = dfs(e.v,min(res,e.c - e.f)); e.f += f; edge[i^1].f -= f; flow += f; res -= f; } } return flow; } int maxflow(int _s, int _t) { s = _s, t = _t; int flow = 0; while(bfs()) { for(int i = 0; i < n; ++i) cur[i] = head[i]; flow += dfs(s,INF); } return flow; } } int main() { int n,m; scanf("%d%d",&n,&m); int s = 0, t = n + 1; Dinic::init(t+1); int x,y; while(~scanf("%d%d",&x,&y)) Dinic::adde(x,y,1); for(int i = 1; i <= n; ++i) if(i <= m) Dinic::adde(s,i,1); else Dinic::adde(i,t,1); printf("%d\n",Dinic::maxflow(s,t)); return 0; } |