AC日记——Collectors Problem uva 10779

思路：

　　最大流；

　　s向所有的贴纸的种类连边，流量为Bob拥有的数量；

　　然后，Bob的朋友如果没有这种贴纸，则这种贴纸向bob的朋友连边，容量1；

　　如果bob的朋友的贴纸很多大于1，向该贴纸的种类连边，容量数量-1；

　　所有贴纸的种类向t连边，容量1；

代码：

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

#define maxn 1005

#define maxque 100005

#define INF 0x7fffffff

int V[maxque],F[maxque],cnt,s,t,num[maxn][maxn];

int n,m,head[maxn],que[maxque],E[maxque],ans,deep[maxn];

inline void in(int &now)

{

    char Cget=getchar();now=;

    while(Cget>''||Cget<'') Cget=getchar();

    while(Cget>=''&&Cget<='')

    {

        now=now*+Cget-'';

        Cget=getchar();

    }

}

inline void edge_add(int u,int v,int f)

{

    E[++cnt]=head[u],V[cnt]=v,F[cnt]=f,head[u]=cnt;

    E[++cnt]=head[v],V[cnt]=u,F[cnt]=,head[v]=cnt;

}

inline bool bfs()

{

    for(int i=s;i<=t;i++) deep[i]=-;

    int h=,tail=,now;que[h]=s,deep[s]=;

    while(h<tail)

    {

        now=que[h++];

        for(int i=head[now];i;i=E[i])

        {

            if(deep[V[i]]<&&F[i]>)

            {

                deep[V[i]]=deep[now]+;

                if(V[i]==t) return true;

                que[tail++]=V[i];

            }

        }

    }

    return false;

}

inline int flowing(int now,int flow)

{

    if(now==t||flow<=) return flow;

    int oldflow=;

    for(int i=head[now];i;i=E[i])

    {

        if(F[i]&&deep[V[i]]==deep[now]+)

        {

            int pos=flowing(V[i],min(flow,F[i]));

            flow-=pos,oldflow+=pos,F[i]-=pos,F[i^]+=pos;

            if(flow==) return oldflow;

        }

    }

    if(oldflow==) deep[now]=-;

    return oldflow;

}

int main()

{

    int T;in(T);

    for(int v=;v<=T;v++)

    {

        cnt=,in(n),in(m),s=,t=n+m+,ans=;int pos,num_;

        memset(num,,sizeof(num)),memset(head,,sizeof(head));

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

        {

            in(num_);

            for(int j=;j<=num_;j++) in(pos),num[i][pos]++;

        }

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

        {

            edge_add(n+i,t,);

            if(num[][i]) edge_add(s,n+i,num[][i]);

        }

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

        {

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

            {

                if(num[i][j])

                {

                    if(num[i][j]>) edge_add(i,j+n,num[i][j]-);

                }

                else edge_add(j+n,i,);

            }

        }

        while(bfs()) ans+=flowing(s,INF);

        printf("Case #%d: %d\n",v,ans);

    }

    return ;

}

巴特西

AC日记——Collectors Problem uva 10779

最新文章

热门文章