dinic TLE 50pts 求助
查看原帖
dinic TLE 50pts 求助
448887
cancan123456楼主2023/1/14 14:36
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
struct Edge {
	int v, w, next;
};
int n, p, q;
int room[105][105], food[105][105];
void input() {
	scanf("%d %d %d", &n, &p, &q);
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= p; j++) {
			scanf("%d", &room[i][j]);
		}
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= q; j++) {
			scanf("%d", &food[i][j]);
		}
	}
}
struct Graph {
	Edge edge[3000005 * 2];
	int head[405];
	int cnt = 1;
	void __add_edge(int u, int v, int w) {
		cnt++;
		edge[cnt].v = v;
		edge[cnt].w = w;
		edge[cnt].next = head[u];
		head[u] = cnt;
	}
	void add_edge(int u, int v, int w) {
		__add_edge(u, v, w);
		__add_edge(v, u, 0);
	}
	int s, t;
	int dep[405];
	int min(int a, int b) {
		return a < b ? a : b;
	}
	bool bfs() {
		memset(dep, 0, sizeof(dep));
		dep[s] = 0;
		queue < int > q;
		q.push(s);
		while (!q.empty()) {
			int u = q.front();
			q.pop();
			for (int i = head[u]; i; i = edge[i].next) {
				int v = edge[i].v, w = edge[i].w;
				if (w > 0 && dep[v] == 0) {
					dep[v] = dep[u] + 1;
					q.push(v);
				}
			}
		}
		return dep[t] != 0;
	}
	int dfs(int u, int flow = 0x7fffffff) {
		if (u == t) {
			return flow;
		}
		int used = 0;
		for (int i = head[u]; i && flow; i = edge[i].next) {
			int v = edge[i].v, w = edge[i].w;
			if (dep[v] == dep[u] + 1 && w > 0) {
				int c = dfs(v, min(flow, w));
				if (c > 0) {
					edge[i].w -= c;
					edge[i ^ 1].w += c;
					flow -= c;
					used += c;
				}
			}
		}
		return used;
	}
	int max_flow = 0;
	void dinic() {
		while (bfs()) {
			max_flow += dfs(s);
		}
	}
	void init() {
		s = p + 2 * n + q + 1;
		t = p + 2 * n + q + 2;
		for (int i = 1; i <= p; i++) {
			add_edge(s, i, 1);
		}
		for (int i = 1; i <= p; i++) {
			for (int j = 1; j <= n; j++) {
				if (room[j][i] == 1) {
					add_edge(i, j + p, 1);
				}
			}
		}
		for (int i = 1; i <= n; i++) {
			add_edge(i + p, i + p + n, 1);
		}
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= q; j++) {
				if (food[i][j] == 1) {
					add_edge(i + p + n, j + p + 2 * n, 1);
				}
			}
		}
		for (int i = 1; i <= q; i++) {
			add_edge(i + p + 2 * n, t, 1);
		}
	}
} g;
signed main() {
	input();
	g.init();
	g.dinic();
	printf("%d", g.max_flow);
	return 0;
}
2023/1/14 14:36
加载中...