「Luogu1402」酒店之王

传送门

Luogu

解题思路

网络流板子题。

建图细节见代码，也可以参考这道差不多的题

细节注意事项

咕咕咕。

参考代码

#include <algorithm>

#include <iostream>

#include <cstring>

#include <cstdio>

#include <cctype>

#include <cmath>

#include <ctime>

#include <queue>

#define rg register

using namespace std;

template < class T > inline void read(T& s) {

	s = 0; int f = 0; char c = getchar();

	while (!isdigit(c)) f |= c == '-', c = getchar();

	while (isdigit(c)) s = s * 10 + c - 48, c = getchar();

	s = f ? -s : s;

}

const int _ = 502;

const int __ = 30002;

const int INF = 2147483647;

int tot = 1, head[_], nxt[__ << 1], ver[__ << 1], cap[__ << 1];

inline void Add_edge(int u, int v, int d)

{ nxt[++tot] = head[u], head[u] = tot, ver[tot] = v, cap[tot] = d; }

inline void link(int u, int v, int d) { Add_edge(u, v, d), Add_edge(v, u, 0); }

int n, p, q, s, t, dep[_], cur[_];

inline int bfs() {

	static queue < int > Q;

	memset(dep, 0, sizeof (int) * (t - s + 1));

	dep[s] = 1, Q.push(s);

	while (!Q.empty()) {

		int u = Q.front(); Q.pop();

		for (rg int i = head[u]; i; i = nxt[i]) {

			int v = ver[i];

			if (dep[v] == 0 && cap[i] > 0)

				dep[v] = dep[u] + 1, Q.push(v);

		}

	}

	return dep[t] > 0;

}

inline int dfs(int u, int flow) {

	if (u == t) return flow;

	for (rg int& i = cur[u]; i; i = nxt[i]) {

		int v = ver[i];

		if (dep[v] == dep[u] + 1 && cap[i] > 0) {

			int res = dfs(v, min(flow, cap[i]));

			if (res) { cap[i] -= res, cap[i ^ 1] += res; return res; }

		}

	}

}

inline int Dinic() {

	int res = 0;

	while (bfs()) {

		for (rg int i = s; i <= t; ++i) cur[i] = head[i];

		while (int d = dfs(s, INF)) res += d;

	}

	return res;

}

int main() {

#ifndef ONLINE_JUDGE

	freopen("cpp.in", "r", stdin);

	freopen("cpp.out", "w", stdout);

#endif

	read(n), read(p), read(q);

	s = 0, t = p + 2 * n + q + 1;

	int f;

	for (rg int i = 1; i <= n; ++i)

		for (rg int j = 1; j <= p; ++j) {

			read(f); if (f) link(j, i + p, 1);

		}

	for (rg int i = 1; i <= n; ++i)

		for (rg int j = 1; j <= q; ++j) {

			read(f); if (f) link(i + p + n, j + p + 2 * n, 1);

		}

	for (rg int i = 1; i <= n; ++i) link(i + p, i + p + n, 1);

	for (rg int i = 1; i <= p; ++i) link(s, i, 1);

	for (rg int i = 1; i <= q; ++i) link(i + p + 2 * n, t, 1);

	printf("%d\n", Dinic());

	return 0;

}

完结撒花 \(qwq\)

巴特西

「Luogu1402」酒店之王

解题思路

细节注意事项

参考代码

最新文章

热门文章