【题解】搭配飞行员网络流24题二分图最大匹配

Prelude

传送到LOJ
这是一道二分图最大匹配的裸题，直接水过去就好。。。

Solution

从\(S\)向每个正驾驶员连边，从正驾驶员向可以同机飞行的副驾驶员连边，从每个副驾驶员向\(T\)连边，所有边容量均为1，网络最大流即为答案。

Code

#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;
}

#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;

}