不是妹子但求调
查看原帖
不是妹子但求调
182792
Jie_Rans楼主2024/9/29 22:32
#include <bits/stdc++.h>
#define INF 10000000
using namespace std;
inline int read() {
	int x = 0, f = 1;
	char ch = getchar();
	while (ch < '0' || ch > '9') {
		if (ch == '-') f = -1;
		ch = getchar();
	}
	while (ch >= '0' && ch <= '9') {
		x = x * 10 + ch - '0';
		ch = getchar();
	}
	return x * f;
}
void write(int x) {
	if (x < 0) {
		putchar('-');
		x = -x;
	}
	if (x > 9) write(x / 10);
	putchar(x % 10 + '0');
}
const int N = 4010, M = 4010;
int n, s, t, m;
int ver[M], edge[M], nxt[M], h[N], tot = 1;
void addedge(int x, int y, int z) {
	ver[++ tot] = y; edge[tot] = z; nxt[tot] = h[x]; h[x] = tot;
	ver[++ tot] = x; edge[tot] = 0; nxt[tot] = h[y]; h[y] = tot;	
}
int d[N], now[N];
bool bfs() {
	queue<int> q;
	q.push(s); d[s] = 1; now[s] = h[s];
	memset(d, 0, sizeof(d));
	while (q.size()) {
		int x = q.front();
		q.pop();
		for (int i = h[x]; i; i = nxt[i]) {
			int y = ver[i], z = edge[i];
			if (!d[y] && z) {
				d[y] = d[x] + 1;
				q.push(y);
				now[y] = h[y];
				if (y == t) return true;
			}
		}
	}
	return false;
}
int dinic(int x, int flow) {

	if (x == t) return flow;
	int i, k, rest = flow;
	for (i = now[x]; i; i = nxt[i]) {
		int y = ver[i], z = edge[i];
		if (d[y] == d[x] + 1 && z) {
			k = dinic(y, min(rest, z));
			if (!k) d[y] = 0;
			edge[i] -= k;
			edge[i ^ 1] += k;
			rest -= k;
		}
	}
	now[x] = i;
	return flow - rest;
}
int main() {
	freopen("test.in", "r", stdin);
	freopen("test.out", "w",stdout);
	n = read();
	s = n + 1; t = n + 2;
	for (int i = 1; i <= n; i ++) {
		int x = read();
		addedge(s, i, x);
	}
	for (int i = 1; i <= n; i ++) {
		int x = read();
		addedge(i, t, x);
	}
	m = read();
	for (int i = 1; i <= m; i ++) {
		int k = read(), x = read(), y = read();
		addedge(s, n + 2 + i, x);
		addedge(n + 2 + i + m, t, y);
		for (int j = 1; j <= k; j ++) {
			int num = read();
			addedge(n + 2 + i, num, INF);
			addedge(num , n + 2 + i + m, INF);
		}
	}
	int flow, maxflow = 0;
	while (bfs())
		while (flow = dinic(s, 10001))
			maxflow += flow;
	write(maxflow);
	return 0;
}	
2024/9/29 22:32
加载中...