【uva10779】收集者的难题

按照题意建模就行了。

#include<bits/stdc++.h>

#define naive 0

#define inf 1000000007

using namespace std;

int n,m,T,a[][],head[],tot,qwq,level[],ans,s,t;

struct Edge{int u,v,f,next;}G[];

inline void addedge(int u,int v,int f){

    G[tot].u=u;G[tot].v=v;G[tot].f=f;G[tot].next=head[u];head[u]=tot++;

    G[tot].u=v;G[tot].v=u;G[tot].f=;G[tot].next=head[v];head[v]=tot++;

}

inline bool bfs(){

    memset(level,naive,sizeof(level));queue<int>q;

    q.push(s);level[s]=;

    while(!q.empty()){

        int u=q.front();q.pop();

        if(u==t)return ;

        for(int i=head[u];~i;i=G[i].next){

            int v=G[i].v,f=G[i].f;

            if(f&&!level[v])level[v]=level[u]+,q.push(v);

        }

    }

    return naive;

}

int dfs(int u,int maxf,int t){

    if(u==t)return maxf;int rat=;

    for(int i=head[u];~i&&rat<maxf;i=G[i].next){

        int v=G[i].v,f=G[i].f;

        if(f&&level[v]==level[u]+){

            f=dfs(v,min(f,maxf-rat),t);

            rat+=f;G[i].f-=f;G[i^].f+=f;

        }

    }

    if(!rat)level[u]=inf;

    return rat;

}

inline int dinic(){

    int ans=;while(bfs())ans+=dfs(s,inf,t);

    return ans;

}

inline int read(){

    int f=,x=naive;char ch;

    do{ch=getchar();if(ch=='-')f=-;}while(ch<''||ch>'');

    do{x=x*+ch-'';ch=getchar();}while(ch>=''&&ch<='');

    return f*x;

}

int main(){

    int T=read();

    while(T--){t=;

        n=read();m=read();memset(head,-,sizeof(head));tot=naive;memset(a,,sizeof(a));

        ans=;

        for(int i=;i<=n;i++){int x=read();while(x--)a[i][read()]++;}

        for(int i=;i<=m;i++)addedge(s,i,a[][i]);

        for(int i=;i<=n;i++)for(int j=;j<=m;j++)

        if(a[i][j]>)addedge(i+m,j,a[i][j]-);

        for(int i=;i<=n;i++)for(int j=;j<=m;j++)if(!a[i][j])addedge(j,i+m,);

        for(int i=;i<=m;i++)addedge(i,t,);

        ans=dinic();printf("Case #%d: %d\n",++qwq,ans);

    }

}