大意不在赘述。
思路:我去网上搜拆点的一般用法时,搜到了这一道题,我在一本书籍上看到了一道非常相似的一道题,只不过那道题食物与饮料的容量为1,这里为任意值,于是YY之后,就AC了。注意一点,就是一个人只能拿一种食物或者饮料,所以我们把点权转换为边权,即我们需要把人拆点为A与A'。
建图的大概思路:添加一个超级源点、汇点,把食物、人、饮料分为B、A、C,我们将源点s与B中所有的点连一条容量为1的边,将C中到汇点连一条容量为1的边。然后把A中的点拆为A,A',如果A喜欢B中的某一种食物的话,连一条边j->A,容量为1,如果A'喜欢C中的某一种饮料的话,则连一条边A'->j,容量为1。最后我们把所有的A->A'连一条边,容量为1。
#include <iostream> #include <cstdlib> #include <cstdio> #include <cstring> #include <string> using namespace std; const int MAXN = 10010; const int MAXM = 400010; const int INF = 0x3f3f3f3f; struct Edge { int v, f; int next; }edge[MAXM]; int n, nf, nd; int cnt; int s, t; int first[MAXN], level[MAXN]; int q[MAXN]; char str[3000]; void init() { cnt = 0; memset(first, -1, sizeof(first)); } void read_graph(int u, int v, int f) { edge[cnt].v = v, edge[cnt].f = f; edge[cnt].next = first[u], first[u] = cnt++; edge[cnt].v = u, edge[cnt].f = 0; edge[cnt].next = first[v], first[v] = cnt++; } int bfs(int s, int t) { memset(level, 0, sizeof(level)); level[s] = 1; int front = 0, rear = 1; q[front] = s; while(front < rear) { int x = q[front++]; if(x == t) return 1; for(int e = first[x]; e != -1; e = edge[e].next) { int v = edge[e].v, f = edge[e].f; if(!level[v] && f) { level[v] = level[x] + 1; q[rear++] = v; } } } return 0; } int dfs(int u, int maxf, int t) { if(u == t) return maxf; int ret = 0; for(int e = first[u]; e != -1; e = edge[e].next) { int v = edge[e].v, f = edge[e].f; if(level[v] == level[u] + 1 && f) { int Min = min(maxf-ret, f); f = dfs(v, Min, t); edge[e].f -= f; edge[e^1].f += f; ret += f; if(ret == maxf) return ret; } } return ret; } int Dinic(int s, int t) { int ans = 0; while(bfs(s, t)) ans += dfs(s, INF, t); return ans; } void read_case() { init(); s = 0, t = nf+nd+n+n+1; for(int i = 1; i <= n; i++) { int A = nf+nd+i, A1 = nf+nd+n+i; read_graph(A, A1, 1); } for(int i = 1; i <= nf; i++) { int f; scanf("%d", &f); read_graph(s, i, f); } for(int i = 1; i <= nd; i++) { int f; scanf("%d", &f); read_graph(i+nf, t, f); } for(int i = 1; i <= n; i++) { int A = nf+nd+i; scanf("%s", str+1); for(int j = 1; str[j]; j++) { if(str[j] == 'Y') { read_graph(j, A, 1); } } } for(int i = 1; i <= n; i++) { int A1 = nf+nd+n+i; scanf("%s", str+1); for(int j = 1; str[j]; j++) { if(str[j] == 'Y') { read_graph(A1, j+nf, 1); } } } } void solve() { read_case(); int ans = Dinic(s, t); printf("%d\n", ans); } int main() { while(~scanf("%d%d%d", &n, &nf, &nd)) { solve(); } return 0; }