输入
4 3 1 2 1 2 2 1 2 1 3 1 3 2 1 2 1
输出
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 cate slove._init(1007); for(int i=1; i<=n; i++) { int cnt = read; for(int j=1; j<=cnt; j++) { int u = read;// toy id slove.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;// r slove.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 id solve.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;// r solve.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; } /** **/
