80pts求助
查看原帖
80pts求助
573363
Jerryfish楼主2022/10/9 18:15
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;

const int N = 405;

int n, m, k, G[N][N], Ans = 0;
int st[N], Prev[N];
int x, y, z;
int s = 0, t;

int bfs() {
	memset(st, 0, sizeof st);
	memset(Prev, 0, sizeof Prev);
	queue< int > q;
	q.push(s);
	st[s] = 1;
	bool isleast = 0;
	while (q.size()7) {
		int u = q.front();
		q.pop();
		bool f = 0;
		for (int i = 0; i <= t; ++ i )
			if (G[u][i] > 0 && !st[i]) {
				Prev[i] = u;
				st[i] = 1;
				if (i == t) {
					f = 1;
					isleast = 1;
					break;
				} else q.push(i);
			}
		if (f) break;
	}
	if (!isleast) return 0;
	int u = t, least_flow = 2e9;
	while (Prev[u]) {
		least_flow = min(least_flow, G[Prev[u]][u]);
		u = Prev[u];
	}
	u = t;
	while (Prev[u]) {
		G[u][Prev[u]] += least_flow;
		G[Prev[u]][u] -= least_flow;
		u = Prev[u];
	}
	return least_flow;
}

int main() {
	int f, d;
	freopen("ttt.txt")
	cin >> n >> m >> k;
	t = n + n + m + k + 1;
	for (int i = 1; i <= k; ++ i ) G[s][i] = 1;
	for (int i = 1; i <= m; ++ i ) G[2 * n + k + i][t] = 1;
	for (int i = 1; i <= n; ++ i ) G[i + k][i + k + n] = 1;
	for (int i = 1; i <= n; ++ i ) {
		scanf("%d%d", &f, &d);
		int F, D;
		for (int j = 1; j <= f; ++ j )
			scanf("%d", &F), G[i + k + n][F + 2 * n + k] = 1;
		for (int j = 1; j <= d; ++ j )
			scanf("%d", &D), G[D][i + k] = 1;

	}

	int Least_flow = 0, tmp;
	while (tmp = bfs()) Least_flow += tmp;
	cout << Least_flow;

	return 0;
}
2022/10/9 18:15
加载中...