uva 10779 - Collector's Problem

Collector's Problem

Input: standard input
Output: standard output
Time Limit: 5 seconds

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 k_i<=50 indicating how many stickers person i has.
Then follows k_i 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.

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

 

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.

---

Problem setter: Adrian Kuegel

network flow,
A. 建模:
   1. source->每一個物品，容量為主角擁有物品的物量
   2. 每一個物品->其他朋友，容量為1,如果朋友沒有此物品的話
   3. 其他朋友->每一個物品，容量為n-1, 其中n為朋友擁有此物品之數量(>0時)
   4. 每一個物品->sink, 容量為1
B. 跑最大流

#include<stdio.h>
#include<cstring>
#include<string>
#include<vector>
#include<sstream>
#define REP(i, b, n) for (int i = b; i < n; i++)
#define rep(i,n) REP(i, 0, n)
#define DBG 0
#define INF int(1e18)
#define MAXN 40
#define MAXM 800
using namespace std;

int N,M,e=0,RES,cases=1;
int stks[10][25];
int v[MAXM],head[MAXN],cap[MAXM],next[MAXM],work[MAXN],p[MAXN],pe[MAXN],pf[MAXN],dis[MAXN];
int q[MAXN];
void addedge(int a,int b,int K){
    v[e]=b,next[e]=head[a],head[a]=e,cap[e]=K,e++;
    v[e]=a,next[e]=head[b],head[b]=e,cap[e]=0,e++;
}
bool BFS(){
    int a,b,c,qr=0,qf=0;
    q[qf++]=0;
    memset(dis,-1,sizeof(dis));
    dis[0]=0;
    for(qr=0;qr<qf;){
        b=q[qr++];
        if(DBG)printf("BFS: %d\n",b);
        for(a=head[b];a>=0;a=next[a]){
            if(dis[v[a]]<0&&cap[a]){
                dis[v[a]]=dis[b]+1;
                if(DBG)printf("b: %d %d cap %d (%d)\n",v[a],dis[v[a]],cap[a],a);
                if(v[a]==1)return 1;
                q[qf++]=v[a];
            }
        }
    }
    return 0;
}
void dinic(){
    int a,b,c,f;
    while(BFS()){
        c=0,f=INF;
        memcpy(work,head,sizeof(head));
        while(1){
            if(DBG)printf("dinic %d %d\n",c,dis[c]);
            for(a=work[c];a>=0;a=next[a]){
                if(DBG)printf("b %d (%d)\n",v[a],dis[v[a]]);
                if(cap[a]&&dis[v[a]]==dis[c]+1){b=v[a];break;}
            }
            if(a>=0)work[c]=next[a]; else work[c]=-1;
            if(a>=0){
                if(b==1){
                    if(DBG)printf("RES++\n");
                    pe[b]=a,p[b]=c,RES++;
                    for(;b!=0;b=p[b])cap[pe[b]]--,cap[pe[b]^1]++;
                    c=0,f=INF;
                }
                else{
                    pf[b]=f,p[b]=c,pe[b]=a;
                    f=min(f,cap[a]);
                    c=b;
                }
            }
            else{
                if(c==0)break;
                f=pf[c];
                c=p[c];
            }
        }
    }
}
void ans(){
    RES=0;
    dinic();
    printf("Case #%d: %d\n",cases++,RES);
}
void addNodes(){
    rep(i,M){
        if(DBG)printf("ae %d %d %d\n",0,i+1,stks[0][i]);
        addedge(0,i+2,stks[0][i]);}
    rep(i,M)rep(j,N-1){
        if(!stks[j+1][i]){addedge(i+2,j+2+M,1);if(DBG)printf("ae %d %d %d\n",i+1,j+1,1);}
        if(stks[j+1][i]>1){addedge(j+2+M,i+2,stks[j+1][i]-1);
                if(DBG)printf("ae (%d %d) %d\n",j+1,1+i,stks[j+1][i]-1);}
    }
    rep(i,M)addedge(i+2,1,1);
}
int main(){
    int n,a,b,c,cases=1;
    stringstream buf;
    char chs[200];
    string s;
    scanf("%d",&n);
    rep(i,n){
        scanf("%d%d ",&N,&M);
        e=0,memset(head,-1,sizeof(head)),memset(stks,0,sizeof(stks));
        rep(i,N){
            fgets(chs,200,stdin);
            if(chs[strlen(chs)-1]=='\n')chs[strlen(chs)-1]='\0';
            buf.clear(),buf.str(chs),buf>>a;
            rep(j,a)buf>>b,b--,stks[i][b]++;
        }
        addNodes();
        ans();
    }
}