[洛谷P3701]「伪模板」主席树

#include <cstdio>
#include <cstring>
#define maxn 111 << 1
#define maxm 111 * 111
const int inf = 0x3f3f3f3f;
int S[5][5] = {
	{0, 1, 1, 0, 0},
	{0, 0, 1, 1, 0},
	{0, 0, 0, 1, 1},
	{1, 0, 0, 0, 1},
	{1, 1, 0, 0, 0}
};
int st, ed;
inline int min(int a, int b) {return a < b ? a : b;}
namespace Dinic {
	int st, ed, sz;
	int head[maxn], cnt = 2;
	struct Edge {
		int to, nxt, w;
	} e[maxm << 1];
	inline void add(int a, int b, int c) {
		e[cnt] = (Edge) {b, head[a], c}; head[a] = cnt;
		e[cnt ^ 1] = (Edge) {a, head[b], 0}; head[b] = cnt ^ 1;
		cnt += 2;
	}
	int d[maxn], q[maxn], h, t;
	inline bool bfs() {
		memset(d, 0, sz);
		d[q[h = t = 0] = st] = 1;
		while (h <= t) {
			int u = q[h++];
//			printf("u:%d\n", u);
			if (u == ed) return true;
			for (int i = head[u]; i; i = e[i].nxt) {
				int v = e[i].to;
				if (!d[v] && e[i].w) {
					d[v] = d[u] + 1;
//					printf("v: %d %d\n", v, d[v]);
					q[++t] = v;
				}
			}
		}
//		printf("d[ed]:%d\n", d[ed]);
		return d[ed];
	}
	int dfs(int x, int low) {
		if (!low || x == ed) return low;
		int res = 0, w;
		for (int i = head[x]; i; i = e[i].nxt) {
			int v = e[i].to;
			if (d[v] == d[x] + 1 && e[i].w) {
				w = dfs(v, min(e[i].w, low - res));
				res += w;
				e[i].w -= w;
				e[i ^ 1].w += w;
				if (res == low) return low;
			}
		}
		if (!res) d[x] = -1;
		return res;
	}
	inline int dinic(int ST, int ED) {
		st = ST, ed = ED, sz = sizeof d;
		int ans = 0;
		while (bfs()) ans += dfs(st, inf); //, printf("%d\n", ans);
		return ans;
	}
}
int n, m, A, B;
inline int get(char *s) {
	if (*s == ‘J‘) return 0;
	if (*s == ‘H‘) return 1;
	if (*s == ‘W‘) return 2;
	if (*s == ‘E‘) return 3;
	if (*s == ‘Y‘) return 4;
	return 20040826;
}
char a[maxn][10], b[maxn][10];
int main() {
	scanf("%d%d", &n, &m);
	st = 0, ed = n << 1 | 1;
	for (int i = 1; i <= n; i++) scanf("%s", a[i]), A += *a[i] == ‘Y‘;
	for (int i = 1; i <= n; i++) scanf("%s", b[i]), B += *b[i] == ‘Y‘;
	for (int i = 1, x; i <= n; i++) {
		scanf("%d", &x);
		Dinic::add(st, i, x + (*a[i] == ‘J‘ ? A : 0));
	}
	for (int i = 1, x; i <= n; i++) {
		scanf("%d", &x);
		Dinic::add(i + n, ed, x + (*b[i] == ‘J‘ ? B : 0));
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (S[get(a[i])][get(b[j])]) Dinic::add(i, j + n, 1); //, printf("%d %d :%c %c\n", i, j, *a[i], *b[j]);
		}
	}
	printf("%d\n", min(Dinic::dinic(st, ed), m));
	return 0;
}