[CF Gym101196

CF Gym101196"/>

[CF Gym101196

题目链接

输入

4 3 1
2 1 2
2 1 2
1 3
1 3
2 1 2 1

输出

2

题目大意：

小孩要玩玩具，一些玩具是属于一定的种类的
但是小孩只能够玩每种种类的一部分玩具，并且小孩并不会喜欢所有的玩具，每个小孩都有自己喜欢玩的玩具，问最多能够有多少个小孩被满足

输入n代表小花子的数量，m玩具的数量，p玩具种类的数量
然后是n行{
在这n行的第i行中：
每行一个k，然后是k个数，代表第i个孩子喜欢玩的k个玩具的编号
}
然后是p行{
在这p行的第i行中：
每行有一个l，然后是l个数，最后是r 代表这l个玩具属于种类i，并且这个种类最多用r个（小孩只能够玩每种种类的一部分玩具）
}
并且最重要的一句话：
Toys can be in at most one category and any toy not listed in these p lines is not in any toy category and all of them can be used. No toy number appears more than once on any line.
玩具最多属于一个种类，如果说有的玩具没有被划分到任意一个种类当中，都可以被任意的玩耍。并且保证所有的玩具只在一行中出现一次

接下来就是建图了：
确定源点和汇点分别为1001、1002
小孩要玩玩具=》将小孩和玩具之间建立容量为1的边
玩具属于{玩具的种类} =》 将玩具和种类建议容量为1的边（注意统计没有被添加在种类中的玩具，可以随便玩）
将源点与玩具的种类之间建立容量为r的边（种类最多用r个（小孩只能够玩每种种类的一部分玩具））
将源点与可以随意玩的玩具之间建立容量为1的边
最后将小孩与汇点1002相连，建立容量为1的边

最终求得源点1001与汇点1002的最大流即可获得最大的能够满足的小孩的数量

EK_code:

struct Edge {int u, v;ll cap, flow;Edge(int uu, int vv, ll _cap, ll _flow) {u = uu, v = vv, cap = _cap, flow = _flow;}
};
struct EdmondsKarp {ll n, m;vector<Edge> edges;vector<int> G[maxn];ll a[maxn], p[maxn];void _init(int n) {for (int i = 0; i <= n; i++) G[i].clear();edges.clear();}void add(int u, int v, ll cap) {edges.push_back(Edge(u, v, cap, 0));edges.push_back(Edge(v, u, 0, 0));m = edges.size();G[u].push_back(m - 2);G[v].push_back(m - 1);}ll maxFlow(int s, int t) {ll Flow = 0;while (true) {memset(a, 0, sizeof a);queue<int> que;que.push(s);a[s] = INF;while (que.size()) {int u = que.front();que.pop();for (int i = 0; i < G[u].size(); i++) {int id = G[u][i];Edge &e = edges[id];///不加&也是可以的int to = e.v;if (!a[to] && e.cap > e.flow) {p[to] = id;a[to] = min(a[u], e.cap - e.flow);que.push(to);}}if (a[t]) break;}if (!a[t]) break;for (int u = t; u != s; u = edges[p[u]].u) {edges[p[u]].flow += a[t];edges[p[u] ^ 1].flow -= a[t];}Flow += a[t];}return Flow;}
} slove;
int n, m, s, t;
int mp[maxn];
int main() {/**cin >> n >> m >> s >> t;slove.init(n);slove.n = n;for (int i = 1; i <= m; i++) {int u = read, v = read;ll cap = read;slove.add(u,v,cap);}cout << slove.maxFlow(s,t) <<endl;**/int p;n = read,m = read,p = read;// n child m toy p cateslove._init(1007);for(int i=1; i<=n; i++) {int cnt = read;for(int j=1; j<=cnt; j++) {int u = read;// toy idslove.add(u,m+i,1);// child <-> toy cap = 1 ok}}for(int i=1; i<=n; i++) {slove.add(i+m, 1002, 1);// child <-> end cap = 1; ok}for(int i=1; i<=p; i++) {int l = read;for(int j=1; j<=l; j++) {int v = read;mp[v] = 1;slove.add(m+n+i,v,1);// cate <-> toy cap = 1; ok}int amount = read;// rslove.add(1001,n+m+i,amount);// 1001 <->cate cap = amount; ok}for(int i=1; i<=m; i++) {if(mp[i] == 0) {slove.add(1001,i,1);// 1001 <-> toy cap = 1;}}int ans = slove.maxFlow(1001,1002);cout << ans << endl;return 0;
}/**
4 3 1
2 1 2
2 1 2
1 3
1 3
2 1 2 1**/

Dinic_code:

struct Edge {int u, v;ll cap, flow;Edge(int _u, int _v, ll _cap, ll _flow) {u = _u, v = _v;cap = _cap, flow = _flow;}
};
struct Dinic {vector<Edge> edge;vector<int> G[maxn];ll dis[maxn],cur[maxn];int n,s,t;bool vis[maxn];void init(int x,int _s,int _t){n = x;for(int i = 0;i <= n;i++) G[i].clear();s = _s,t = _t;edge.clear();}void add(int u,int v,ll cap){edge.push_back(Edge(u,v,cap,0));edge.push_back(Edge(v,u,0,0));G[u].push_back(edge.size() - 2);G[v].push_back(edge.size() - 1);}bool bfs(int s,int t){queue<int> que;memset(vis,0,sizeof vis);// memset(dis,0,sizeof dis);dis[s] = 0;que.push(s);vis[s] = 1;while(que.size()){int u = que.front();que.pop();for(int i=0;i<G[u].size();i++){int id = G[u][i];int to = edge[id].v;if(!vis[to] && edge[id].cap > edge[id].flow){dis[to] = dis[u] + 1;que.push(to);vis[to] = 1;}}}return vis[t];}ll dfs(int s,int t,ll rest){if(s == t || rest == 0) return rest;ll sum = 0LL;ll Flow = 0, f;for(ll& i = cur[s];i < G[s].size();i ++){Edge& e = edge[G[s][i]];if(dis[s] + 1 == dis[e.v] && (f = dfs(e.v ,t,min(rest,e.cap - e.flow))) > 0){e.flow += f;edge[G[s][i] ^ 1].flow -= f;Flow += f;rest -= f;if(rest == 0) break;}}return Flow;}ll getMaxFlow(int s,int t){ll ans = 0;while(bfs(s,t)) {memset(cur,0,sizeof cur);ans += dfs(s,t,0x3f3f3f3f);}return ans;}
} solve;
int mp[1007];
int main() {int n = read,m = read,p = read;solve.init(1000,1001,1002);for(int i=1; i<=n; i++) {int cnt = read;for(int j=1; j<=cnt; j++) {int u = read;// toy idsolve.add(u,m+i,1);// child <-> toy cap = 1 ok}}for(int i=1; i<=n; i++) {solve.add(i+m, 1002, 1);// child <-> end cap = 1; ok}for(int i=1; i<=p; i++) {int l = read;for(int j=1; j<=l; j++) {int v = read;mp[v] = 1;solve.add(m+n+i,v,1);// cate <-> toy cap = 1; ok}int amount = read;// rsolve.add(1001,n+m+i,amount);// 1001 <-> cate cap = amount; ok}for(int i=1; i<=m; i++) {if(mp[i] == 0) {solve.add(1001,i,1);// 1001 <-> toy cap = 1;}}int ans = solve.getMaxFlow(1001,1002);cout << ans << endl;return 0;
}
/****/