ACM-ICPC Nanjing Onsite 2018 Magic Potion（网络流最大流 + 建图）

There are nn heroes and mm monsters living in an island. The monsters became very vicious these days, so the heroes decided to diminish the monsters in the island. However, the ii-th hero can only kill one monster belonging to the set M_iMi. Joe, the strategist, has kk bottles of magic potion, each of which can buff one hero's power and let him be able to kill one more monster. Since the potion is very powerful, a hero can only take at most one bottle of potion.

Please help Joe find out the maximum number of monsters that can be killed by the heroes if he uses the optimal strategy.

Input

The first line contains three integers n, m, kn,m,k (1 \le n, m, k \le 5001≤n,m,k≤500) \text{---}— the number of heroes, the number of monsters and the number of bottles of potion.

Each of the next nn lines contains one integer t_iti, the size of M_iMi, and the following t_{i}ti integers M_{i, j}Mi,j (1 \le j \le t_i1≤j≤ti), the indices (11-based) of monsters that can be killed by the ii-th hero (1 \le t_i\le m, 1\leq M_{i, j} \le m1≤ti≤m,1≤Mi,j≤m).

Output

Print the maximum number of monsters that can be killed by the heroes.

样例输入1

样例输出1

样例输入2

5 10 2
2 3 10
5 1 3 4 6 10
5 3 4 6 8 9
3 1 9 10
5 1 3 6 7 10

样例输出2

题目来源

ACM-ICPC Nanjing Onsite 2018

题意：

有 n 个奥特曼和 m 个怪兽，给出每个奥特曼可以打败的怪兽列表，一个奥特曼只能打一个怪兽。有 k 瓶药水，喝了药水的奥特曼可以多打一个怪兽，问最多可以打多少怪兽

思路：

网络流最大流。源点 s 连接 n 个奥特曼，汇点 t 连接 m 个怪兽，流量都是1（表示每个奥特曼只能打一次怪兽，每个怪兽最多被打一次）。再建一个表示药水的点 x ，s 到 x 要连一条流量为 k 的边，表示有 k 瓶药水可供使用，点 x 到每个奥特曼都要连一条边，表示每个奥特曼最多喝一瓶药水。跑dinic就完了。

参考：

https://blog.csdn.net/weixin_43828245/article/details/101159078

https://blog.csdn.net/weixin_43901733/article/details/104031734

https://www.cnblogs.com/wrjlinkkkkkk/p/10037923.html

来自上面链接的一张图ヽ(✿ﾟ▽ﾟ)ノ

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int N = 1105;
const int M = 2e4 + 10;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;

int head[N], tot, n, m, s, t;
struct Edge {
    int to, next, cap, flow;
}edge[M];

void init() {
    tot = 2;
    memset(head, -1, sizeof(head));
}

void addedge(int u, int v, int w, int rw = 0) {
    edge[tot].to = v;
    edge[tot].cap = w;
    edge[tot].flow = 0;
    edge[tot].next = head[u];
    head[u] = tot++;

    edge[tot].to = u;
    edge[tot].cap = rw;
    edge[tot].flow = 0;
    edge[tot].next = head[v];
    head[v] = tot++;
}

int Q[N];
int dep[N], cur[N], sta[N]; ///数组cur记录点u之前循环到了哪一条边
bool bfs(int s, int t, int n) {
    int fron = 0, tail = 0;
    memset(dep, -1, sizeof(dep[0]) * (n + 1));
    dep[s] = 0;
    Q[tail++] = s;
    while(fron < tail) {
        int u = Q[fron++];
        for(int i = head[u]; i != -1; i = edge[i].next) {
            int v = edge[i].to;
            if(edge[i].cap > edge[i].flow && dep[v] == -1) {
                dep[v] = dep[u] + 1;
                if(v == t) return true;
                Q[tail++] = v;
            }
        }
    }
    return false;
}

int dinic(int s, int t, int n) {
    int maxflow = 0;
    while(bfs(s, t, n)) {
        for(int i = 0; i <= n; ++i) cur[i] = head[i];
        int u = s, tail = 0;
        while(cur[s] != -1) {
            if(u == t) {
                int tp = inf;
                for(int i = tail - 1; i >= 0; --i)
                    tp = min(tp, edge[sta[i]].cap - edge[sta[i]].flow);
                maxflow += tp;
                for(int i = tail - 1; i >= 0; --i) {
                    edge[sta[i]].flow += tp;
                    edge[sta[i] ^ 1].flow -= tp;
                    if(edge[sta[i]].cap - edge[sta[i]].flow == 0)
                        tail = i;
                }
                u = edge[sta[tail] ^ 1].to;
            }
            else if(cur[u] != -1 && edge[cur[u]].cap > edge[cur[u]].flow && dep[u] + 1 == dep[edge[cur[u]].to]) {
                sta[tail++] = cur[u];
                u = edge[cur[u]].to;
            }
            else {
                while(u != s && cur[u] == -1)
                    u = edge[sta[--tail] ^ 1].to;
                cur[u] = edge[cur[u]].next;
            }
        }
    }
    return maxflow;
}

int main() {
    init();
    int v, w, nn, mm, k, cnt;
    scanf("%d%d%d", &nn, &mm, &k);
    n = nn + mm + 3;
    for(int u = mm + 1; u <= mm + nn; ++u) {
        scanf("%d", &cnt);
        for(int i = 1; i <= cnt; ++i) {
            scanf("%d", &v);
            addedge(u, v, 1);
        }
    }
    for(int u = 1; u <= mm; ++u)
        addedge(u, nn + mm + 2, 1);
    for(int v = mm + 1; v <= mm + nn + 1; ++v) {
        addedge(nn + mm + 1, v, 1);
        addedge(n, v, 1);
    }
    addedge(nn + mm + 1, n, k);
    printf("%d\n", dinic(n - 2, n - 1, n));
    return 0;
}