1 条题解

  • 0
    @ 2022-12-9 7:57:22

    C++ :

    #include<cstdio>
    #include<cstring>
    
    int n,m,i,j,d[302],de[100005],val[302];
    int ch;
    
    inline int getint()
    {
    	for(ch=getchar();ch<'0'||ch>'9';ch=getchar());
    	int i1=ch-'0';
    	for(ch=getchar();ch>='0'&&ch<='9';ch=getchar())i1=((i1<<3)+(i1<<1)+ch-'0');
    	return i1;
    }
    int first[702],nxt[300005],e[300005],tope,ps,pt;
    long long c[300005];
    long long ans;
    
    inline void link(int u0,int v0,long long w0)
    {
    	++tope;
    	e[tope]=v0;
    	nxt[tope]=first[u0];
    	first[u0]=tope;
    	c[tope]=w0;
    	++tope;
    	e[tope]=u0;
    	nxt[tope]=first[v0];
    	first[v0]=tope;
    	c[tope]=0;
    	return;
    }
    
    inline void buildgraph()
    {
    	memset(first,0,sizeof(first));
    	tope=1;
    	int i1,i2;
    	ps=(n<<1)+1;pt=ps+1;
    	for(i1=1;i1<=n;++i1)
    	{
    		link(ps,i1,987654321-val[i1]);
    		ans+=987654321-val[i1];
    		link(i1+n,pt,987654321);
    		for(i2=d[i1-1]+1;i2<=d[i1];++i2)link(i1,de[i2]+n,9876543210654321ll);
    	}
    	return;
    }
    
    int dis[702],cur[702];
    int q[702],lq,rq;
    inline int bfs()
    {
    	memset(dis,-1,sizeof(dis));
    	q[rq=1]=ps;
    	dis[ps]=0;
    	int i1;
    	for(lq=1;lq<=rq;++lq)
    	{
    		cur[q[lq]]=first[q[lq]];
    		for(i1=first[q[lq]];i1;i1=nxt[i1])
    		{
    //			printf("(%d,%d),c=%lld\n",q[lq],e[i1],c[i1]);
    			if((c[i1]<=0)||(dis[e[i1]]>=0))continue;
    			dis[e[i1]]=dis[q[lq]]+1;
    			q[++rq]=e[i1];
    		}
    	}
    	return dis[pt];
    }
    
    inline long long dinic(const int v1,const int v2,const long long x0)
    {
    	if(v1==v2)return x0;
    	int i1;
    	long long i2=x0,i3;
    	for(i1=cur[v1];i1;i1=nxt[i1])
    	{
    		if((c[i1]>0)&&(dis[e[i1]]==dis[v1]+1))
    		{
    			i3=dinic(e[i1],v2,(c[i1]<i2)?c[i1]:i2);
    			if(i3<=0)continue;
    			c[i1]-=i3;
    			c[i1^1]+=i3;
    			i2-=i3;
    			if(i2<=0)break;
    		}
    	}
    	cur[v1]=i1;
    	return x0-i2;
    }
    inline long long maxflow()
    {
    	long long i1=0;
    	while(bfs()>=0)
    	{
    		i1+=dinic(ps,pt,987654321012345ll);
    	}
    	return i1;
    }
    
    int main()
    {
    	n=getint();
    	memset(d,0,sizeof(d));
    	for(i=1;i<=n;++i)
    	{
    		d[i]=getint();
    		d[i]+=d[i-1];
    		for(j=d[i-1]+1;j<=d[i];++j)de[j]=getint();
    	}
    	for(i=1;i<=n;++i)scanf("%d",&val[i]);
    	ans=0;
    	buildgraph();
    	ans-=maxflow();
    	printf("%lld",-ans);
    	return 0;
    }
    

    信息

    ID
    166
    时间
    1000ms
    内存
    512MiB
    难度
    10
    标签
    递交数
    1
    已通过
    1
    上传者