destoon做众筹网站,如何管理网站页面设计,自己网站制作的详细教程,网站建设有几种工具活动 - AcWing
奶牛们在吃饭方面十分挑剔。
每头奶牛都有自己喜欢的食物和饮料#xff0c;并且不会食用其他不喜欢的食物和饮料。
农夫约翰为他的奶牛们做了美味的饭菜#xff0c;但他忘了对照他们的喜好来检查菜单。
虽然他可能无法令所有奶牛满意#xff0c;但他想给尽…活动 - AcWing
奶牛们在吃饭方面十分挑剔。
每头奶牛都有自己喜欢的食物和饮料并且不会食用其他不喜欢的食物和饮料。
农夫约翰为他的奶牛们做了美味的饭菜但他忘了对照他们的喜好来检查菜单。
虽然他可能无法令所有奶牛满意但他想给尽可能多的奶牛提供一顿完整的用餐----既有食物可吃也有饮料可喝。
农夫约翰一共烹制了 F 种食物并提供了 D 种饮料。
约翰共有 N 头奶牛其中第 i 头奶牛有 Fi 种喜欢的食物以及 Di 种喜欢的饮料。
约翰需要给每头奶牛分配一种食物和一种饮料并使得有吃有喝的奶牛数量尽可能大。
每种食物或饮料都只有一份所以只能分配给一头奶牛食用。
输入格式
第一行包含三个整数 N,F,D。
接下来 N 行其中第 i 行描述第 i 头奶牛的饮食喜好首先包含两个整数 Fi 和 Di表示其喜欢的食物和饮料数量然后包含 Fi 个整数表示其喜欢的食物的种类编号最后包含 Di 个整数表示其喜欢的饮料的种类编号。
食物编号从 1 到 F饮料编号从 1 到 D。
输出格式
输出一个整数表示能够有吃有喝的奶牛的最大数量。
数据范围
1≤N,F,D≤100 1≤Fi≤F 1≤Di≤D
输入样例
4 3 3
2 2 1 2 3 1
2 2 2 3 1 2
2 2 1 3 1 2
2 1 1 3 3输出样例
3样例解释
一种使得三头奶牛满意的可行方法是
奶牛 1没饭。 奶牛 2食物 2饮料 2。 奶牛 3食物 1饮料 1。 奶牛 4食物 3饮料 3。
解析
本题与二分图的匹配很像思路也差不多。
首先将点集分成三部分牛饮料食物。建图方式与二分图匹配类似但如果直接按照二分图的方式建图的话将牛放在中间点集就会出现多种饮料和多种食物对应一头牛不能保证流过牛节点的流量为 1。
拆点针对上述问题我们可以使用拆点的方式。上述的问题是由无法确保流过牛的节点的流量为 1 引起的所以针对此类问题我们可以将牛节点拆成两个节点入节点和出节点。两个节点之间连一条容量为 1 的边这样我们就能确保流过一头牛的流量为 1 了。
建图的正确性证明与之前的最大流之二分图匹配的证明类似。 #includeiostream
#includestring
#includecstring
#includecmath
#includectime
#includealgorithm
#includeutility
#includestack
#includequeue
#includevector
#includeset
#includemath.h
#includemap
#includesstream
#includedeque
#includeunordered_map
#includeunordered_set
#includebitset
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pairint, int PII;
const int N 410, M 40610, INF 0x3f3f3f3f;
int n, F, D, S, T;
int h[N], e[M], f[M], ne[M], idx;
int q[N], d[N], cur[N];void add(int a, int b, int c) {e[idx] b, f[idx] c, ne[idx] h[a], h[a] idx;e[idx] a, f[idx] 0, ne[idx] h[b], h[b] idx;
}bool bfs() {int hh 0, tt 0;memset(d, -1, sizeof d);q[0] S, d[S] 0, cur[S] h[S];while (hh tt) {int t q[hh];for (int i h[t]; i ! -1; i ne[i]) {int j e[i];if (d[j] -1 f[i]) {d[j] d[t] 1;cur[j] h[j];if (j T)return 1;q[tt] j;}}}return 0;
}int find(int u, int limit) {if (u T)return limit;int flow 0;for (int i cur[u]; i ! -1 flow limit; i ne[i]) {int j e[i];cur[u] i;if (d[j] d[u] 1 f[i]) {int t find(j, min(f[i], limit - flow));if (!t)d[j] -1;f[i] - t, f[i ^ 1] t, flow t;}}return flow;
}int dinic() {int ret 0, flow;while (bfs())while (flow find(S, INF)) {//cout _____________________ flow endl;ret flow;}return ret;
}int main() {cin n F D;memset(h, -1, sizeof h);S 0, T n * 2 F D 1;for (int i 1; i F; i)add(S, 2 * n i, 1);for (int i 1; i D; i)add(i 2 * n F, T, 1);for (int i 1; i n; i)add(i, i n, 1);for (int i 1,a,b; i n; i) {scanf(%d%d, a, b);for (int j 1,t; j a; j) {scanf(%d, t);add(2 * n t, i, 1);}for (int j 1,t; j b; j) {scanf(%d, t);add(i n, 2 * n F t, 1);}}cout dinic() endl;return 0;
}
