如何做弹幕网站/aso优化

https://cn.vjudge.net/contest/68128#problem/B

题意： 给定n头牛，m个食物，k个饮料，每头牛需要一种自己喜欢的食物+饮料才会满意，问最多能让多少牛满意

二分没有办法，因为牛喜欢的东西有两种，考虑最大流

建图方式：1.把所有食物和源点相连，饮料和汇点相连，且流量为1（保证只有一个）

2.把一头牛拆成两个点，一个点和喜欢的食物相连，一个点和喜欢的饮料相连，且流量为1

3.同一头牛的两个点之间相连，且流量为1

最后就变成了求解最大流的裸题，哇题解者真的是清奇的脑回路%%%%

所以现在意识到了问题，网络流难就难在题目的转化和建图上，建图还好说，主要是转化的思维千奇百怪

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<set>
#include<map>
#include<queue>
#include<cmath>
#define ll long long
#define mod 1000000007
#define inf 0x3f3f3f3f
using namespace std;
const int maxn = 205*2;
int cnt, st, en;
int n, m;
int u, v, w;
struct node
{int to, next, w;
}e[maxn*maxn];
int head[maxn], depth[maxn], cur[maxn];
void init()
{st = 0, en = n;cnt = 0;memset(head, -1, sizeof(head));
}
void addedge(int u, int v, int w)
{e[cnt].w = w;e[cnt].to = v;e[cnt].next = head[u];head[u] = cnt ++;e[cnt].w = 0;e[cnt].to = u;e[cnt].next = head[v];head[v] = cnt ++;
}
int dfs(int u, int flow)
{if(u == en) return flow;for(int& i = cur[u]; ~i; i = e[i].next){if(depth[e[i].to] == depth[u] + 1 && (e[i].w != 0)){int zen = dfs(e[i].to, min(e[i].w, flow));if(zen){e[i].w -= zen;e[i^1].w += zen;return zen;}}}return 0;
}
int bfs()
{queue<int> q;while(! q.empty()) q.pop();memset(depth, 0, sizeof(depth));depth[st] = 1;q.push(st);while(! q.empty()){int h = q.front();q.pop();for(int i = head[h]; ~i; i = e[i].next){if((! depth[e[i].to]) && e[i].w){depth[e[i].to] = depth[h] + 1;q.push(e[i].to);}}}if(depth[en]) return 1;return 0;
}
int dinic()
{int ans = 0;while(bfs()){for(int i = 0; i <= n; i ++)cur[i] = head[i];while(int d = dfs(st, inf))ans += d;}return ans;
}
int main()
{int N, D, F;while(scanf("%d%d%d", &N, &F, &D) != EOF){n = N * 2 + F + D + 1;init();for(int i = 1; i <= F; i ++)addedge(0, i, 1);for(int i = F + 2 * N + 1; i <= F + 2 * N + D; i ++)addedge(i, n, 1);for(int i = 1; i <= N; i ++)addedge(F + 2 * i - 1, F + 2 * i, 1);int a, b, tmp;for(int i = 1; i <= N;i ++){scanf("%d%d", &a, &b);for(int j = 1; j <= a; j ++){scanf("%d", &tmp);addedge(tmp, F + 2 * i - 1, 1);}for(int j = 1; j <= b; j ++){scanf("%d", &tmp);addedge(F + 2 * i, F + 2 * N + tmp, 1);}}printf("%d\n", dinic());}return 0;
}