网络流

1.Bob向他有的贴纸连边，流量为他有的贴纸数量

2.每一种贴纸向汇点连流量为1的边

3.其余人，如果没贴纸i，由i向这个人连一条流量为1的边

4.如果贴纸i数量>1，由这个人向i连一条流量为数量-1的边

#include 
     
      #include 
      
       #include 
       
        using namespace std;const int N = 45;const int M = 650;#define gc getchar()#define oo 999999999int n, m, now, S, T, TI;int head[N], now_head[N], calc[N], dis[N];struct Node{    int u, v, flow, nxt;}G[M];queue 
        
          Q;inline int read(){    int x = 0; char c = gc;    while(c < '0' || c > '9') c = gc;    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = gc;    return x;}inline void add(int u, int v, int flow){    G[now].v = v; G[now].flow = flow; G[now].nxt = head[u]; head[u] = now ++;}inline bool bfs(){    for(int i = S; i <= T; i ++) now_head[i] = head[i], dis[i] = -1;    dis[S] = 0;    while(!Q.empty()) Q.pop();    Q.push(S);    while(!Q.empty()){        int topp = Q.front();        Q.pop();        for(int i = head[topp]; ~ i; i = G[i].nxt){            int v = G[i].v;            if(dis[v] == -1 && G[i].flow > 0){                dis[v] = dis[topp] + 1;                if(v == T) return 1;                Q.push(v);            }                }    }    return 0;}int dfs(int now, int flow){    if(now == T) return flow;    int ret = 0;    for(int & i = now_head[now]; ~ i; i = G[i].nxt){        int v = G[i].v;        if(dis[v] == dis[now] + 1 && G[i].flow > 0){            int f = dfs(v, min(G[i].flow, flow - ret));            if(f) {G[i].flow -= f; G[i ^ 1].flow += f; ret += f; if(ret == flow) break;}        }    }    if(ret != flow) dis[now] = -1;    return ret;}inline int Dinic(){    int ret = 0;    while(bfs()) ret += dfs(S, oo);    return ret;}int main(){    TI = read();    for(int Ti = 1; Ti <= TI; Ti ++){        n = read(); m = read(); now = 0;        T = n + m + 1; S = 1;        for(int i = 0; i <= T; i ++) head[i] = -1;        for(int i = 1; i <= m; i ++) add(n + i, T, 1), add(T, n + i, 0);        int k = read();        for(int i = 1; i <= k; i ++){
   int im = read(); calc[im] ++;}         for(int i = 1; i <= m; i ++) if(calc[i]) add(1, n + i, calc[i]), add(n + i, 1, 0);        for(int i = 1; i <= m; i ++) calc[i] = 0;        for(int i = 2; i <= n; i ++){            int k = read();            for(int j = 1; j <= k; j ++){
   int im = read(); calc[im] ++;}            for(int j = 1; j <= m; j ++)                if(calc[j] > 1) add(i, n + j, calc[j] - 1), add(n + j, i, 0);                else if(!calc[j]) add(n + j, i, 1), add(i, n + j, 0);            for(int j = 1; j <= m; j ++) calc[j] = 0;        }        int answer = Dinic();        printf("Case #%d: %d\n", Ti, answer);    }    return 0;}/*22 56 1 1 1 1 1 13 1 2 23 54 1 2 1 13 2 2 25 1 3 4 4 3*/