UVA10779Collectors Problem

uva 10779 Collectors Problem

Some candy manufacturers put stickers into candy bar packages. Bob and his friends are collecting 
these stickers. They all want as many different stickers as possible, but when they buy a candy bar, 
they don’t know which sticker is inside. 
It happens that one person has duplicates of a certain sticker. Everyone trades duplicates for stickers 
he doesn’t possess. Since all stickers have the same value, the exchange ratio is always 1:1. 
But Bob is clever: he has realized that in some cases it is good for him to trade one of his duplicate 
stickers for a sticker he already possesses. 
Now assume, Bob’s friends will only exchange stickers with Bob, and they will give away only 
duplicate stickers in exchange with different stickers they don’t possess. 
Can you help Bob and tell him the maximum number of different stickers he can get by trading 
stickers with his friends? 

Input 

The first line of input contains the number of cases T (T ≤ 20). The first line of each case contains 
two integers n and m (2 ≤ n ≤ 10, 5 ≤ m ≤ 25). n is the number of people involved (including Bob), 
and m is the number of different stickers available. 
The next n lines describe each person’s stickers; the first of these lines describes Bob’s stickers. 
The i-th of these lines starts with a number ki ≤ 50 indicating how many stickers person i has. 
Then follows ki numbers between 1 and m indicating which stickers person i possesses. 

Output 

For each case, print the test case number together with the maximum number of different stickers Bob 
can get. 

Explanation of the sample output: 

In the first case, no exchange is possible, therefore Bob can have only the sticker with number 1. 
In the second case, Bob can exchange a sticker with number 1 against a sticker with number 2 of 
the second person, and then this sticker against a sticker with number 3 or 4 of the third person, and 
now he has stickers 1, 2 and 3 or 1, 2 and 4. 

Sample Input 

2 
2 5 
6 1 1 1 1 1 1 
3 1 2 2 
3 5 
4 1 2 1 1 
3 2 2 2 
5 1 3 4 4 3 

Sample Output 

Case #1: 1 
Case #2: 3

题意

n个人，m种贴纸，每个人开始都有一些贴纸。

第一个人Bob可以跟任何人交换任何贴纸，其他人只能用重复的贴纸，和Bob交换他们没有的贴纸，Bob最后最多有多少种贴纸

分析

网络流。重点是建图。

Bob做源点好了，汇点新建一个。

Bob和所有贴纸有一条流量为 Bob拥有的贴纸数量的边，所有贴纸都与汇点建一条流量为1的边。

如果其他的人第i张贴纸有x张多余的，那么这个人向i连一条流量为x的边。

如果他第i张贴纸为0，那么i向这个人连一条流量为1的边。

code

include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<iostream>

using namespace std;

const int INF = 1e9;
const int N = 10010;

struct Edge{
    int to,nxt,c;
}e[N];
int q[500100],head[N],cur[N],dis[N],cnt[50][50];
int L,R,S,T,tot = 1;

inline char nc() {
    static char buf[100000],*p1 = buf,*p2 = buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int read() {
    int x = 0,f = 1;char ch = nc();
    for (; ch<'0'||ch>'9'; ch = nc()) if (ch=='-') f = -1;
    for (; ch>='0'&&ch<='9'; ch = nc()) x = x * 10 + ch - '0';
    return x * f;
}
inline void init() {
    tot = 1;memset(head,0,sizeof(head));
    memset(cnt,0,sizeof(cnt));
}
inline void add_edge(int u,int v,int w) {
    e[++tot].to = v,e[tot].c = w,e[tot].nxt = head[u],head[u] = tot;
    e[++tot].to = u,e[tot].c = 0,e[tot].nxt = head[v],head[v] = tot;
}
bool bfs() {
    for (int i=1; i<=T; ++i) {
        cur[i] = head[i];dis[i] = -1;
    }
    L = 1;R = 0;
    q[++R] = S;
    dis[S] = 0;
    while (L <= R) {
        int u = q[L++];
        for (int i=head[u]; i; i=e[i].nxt) {
            int v = e[i].to,c = e[i].c;
            if (dis[v]==-1&&c>0) {
                dis[v] = dis[u] + 1;
                q[++R] = v;
                if (v==T) return true;
            }
        }
    }
    return false;
}
int dfs(int u,int flow) {
    if (u==T) return flow;
    int used = 0;
    for (int &i=cur[u]; i; i=e[i].nxt) {
        int v = e[i].to,c = e[i].c;
        if (dis[v]==dis[u]+1 && c>0) {
            int tmp = dfs(v,min(c,flow-used));
            if (tmp > 0) {
                e[i].c -= tmp;e[i^1].c += tmp;
                used += tmp;
                if (used==flow) break;
            }
        }
    }
    if (used!=flow) dis[u] = -1;
    return used;
}
inline int dinic() {
    int ans = 0;
    while (bfs()) ans += dfs(S,INF);
    return ans;
}
int main() {
    int sum_case = read();
    for (int Case=1; Case<=sum_case; Case++) {
        init();
        int n = read(),m = read();
        S = 1;T = n + m + 1;
        for (int i=1; i<=m; ++i) add_edge(i+n,T,1);
        for (int i=1; i<=n; ++i) {
            int k = read();
            for (int a,j=1; j<=k; ++j) {
                a = read();cnt[i][a]++;
            }
        }
        for (int i=1; i<=m; ++i) 
            if (cnt[1][i]) add_edge(S,i+n,cnt[1][i]);
        for (int i=2; i<=n; ++i) {
            for (int j=1; j<=m; ++j) {
                if (cnt[i][j] > 1) add_edge(i,j+n,cnt[i][j]-1);
                else if (cnt[i][j]==0) add_edge(j+n,i,1);
            }
        }
        printf("Case #%d: %d
",Case,dinic());        
    }
    return 0;
}