1 条题解

  • 0
    @ 2025-9-9 23:46:00

    C++ :

    //SAPËã·¨
    #include<stdio.h>
    #include<string.h>
    #include<algorithm>
    #define inf 9999999999
    #define M 1007
    #define MIN(a,b) a>b?b:a;
    using namespace std;
    struct E
    {
        int v,w,next;
    }edg[500000];
    int dis[2000],gap[2000],head[2000],nodes;
    int sourse,sink,nn;
    void addedge(int u,int v,int w)
    {
        edg[nodes].v=v;
        edg[nodes].w=w;
        edg[nodes].next=head[u];
        head[u]=nodes++;
        edg[nodes].v=u;
        edg[nodes].w=0;
        edg[nodes].next=head[v];
        head[v]=nodes++;
    }
    int dfs(int src,int aug)
    {
        if(src==sink)return aug;
        int left=aug,mindis=nn;
        for(int j=head[src];j!=-1;j=edg[j].next)
        {
        	int v=edg[j].v;
        	if(edg[j].w)
            {
               if(dis[v]+1==dis[src])
               {
                   int minn=MIN(left,edg[j].w);
                   minn=dfs(v,minn);
                   edg[j].w-=minn;
                   edg[j^1].w+=minn;
                   left-=minn;
                   if(dis[sourse]>=nn)return aug-left;
                   if(left==0)break;
               }
               if(dis[v]<mindis)
               mindis=dis[v];
            }
        }
    
            if(left==aug)
            {
                if(!(--gap[dis[src]]))dis[sourse]=nn;
                dis[src]=mindis+1;
                gap[dis[src]]++;
            }
            return aug-left;
    }
    int sap(int s,int e)
    {
        int ans=0;
    	nn=e+1;
        memset(dis,0,sizeof(dis));
        memset(gap,0,sizeof(gap));
        gap[0]=nn;
        sourse=s;
        sink=e;
        while(dis[sourse]<nn)
        ans+=dfs(sourse,inf);
        return ans;
    }
    int main()
    {
            int n,f,d;
            while(scanf("%d%d%d",&n,&f,&d)!=EOF)
            {
    
             memset(head,-1,sizeof(head));
             nodes=0;
             int s=0;
             int i,j;
             int t=f+2*n+1+d;
             int food,drink;
             int a,b;
             for(i=1;i<=n;i++)
             {
                 scanf("%d%d",&food,&drink);
                 for(j=1;j<=food;j++)
                 {
                     scanf("%d",&a);
                     addedge(a,i+f,1);//食物和人
                 }
                 for(j=1;j<=drink;j++)
                 {
                     scanf("%d",&b);
                     addedge(i+f+n,f+2*n+b,1);//人和饮料
                 }
             }
             for(i=1;i<=f;i++)
             {
                 addedge(s,i,1);
             }
             for(i=1;i<=d;i++)
             {
                 addedge(f+2*n+i,t,1);//人和人
             }
             for(i=1;i<=n;i++)
             {
                 addedge(i+f,i+f+n,1);
             }
    
             int anss=sap(s,t);
             printf("%d\n",anss);
            }
        return 0;
    }
    
    
    • 1

    信息

    ID
    934
    时间
    2000ms
    内存
    216MiB
    难度
    (无)
    标签
    递交数
    0
    已通过
    0
    上传者