托米去购物

C++14(g++5.4) 解法, 执行用时: 27ms, 内存消耗: 2424K, 提交时间: 2018-06-01 20:08:28

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1580;
const int M=5e5+88;
const int INF=0x3f3f3f3f;
int head[N],tot,S,T;
int q[N],dis[N],n,m;
bool vis[N];
struct node
{
    int next,v,w;
} e[M<<2];
void add(int u,int v,int w)
{
    e[tot].v=v;
    e[tot].w=w;
    e[tot].next=head[u];
    head[u]=tot++;
}
bool bfs()
{
    memset(dis,-1,sizeof(dis));
    dis[S]=0;
    int l=0,r=0;
    q[r++]=S;
    while(l<r)
    {
        int u=q[l++];
        for(int i=head[u]; ~i; i=e[i].next)
        {
            int v=e[i].v;
            if(dis[v]==-1&&e[i].w>0)
            {
                q[r++]=v;
                dis[v]=dis[u]+1;
                if(v==T) return true;
            }
        }
    }
    return false;
}
int dfs(int s,int low)
{
    if(s==T||!low) return low;
    int ans=low,a;
    for(int i=head[s]; ~i; i=e[i].next)
    {
        if(e[i].w>0&&dis[e[i].v]==dis[s]+1&&(a=dfs(e[i].v,min(e[i].w,ans))))
        {
            e[i].w-=a;
            e[i^1].w+=a;
            ans-=a;
            if(!ans) return low;
        }
    }
    if(low==ans) dis[s]=-1;
    return low-ans;
}
int vt[1250];
int main()
{
	int Ta;
	for(scanf("%d",&Ta);Ta--;){
    scanf("%d%d",&n,&m);
    S=0,T=n+m+1;
    int x,y,ans=0;
    memset(head,-1,sizeof(head));
    tot=0;
    for(int i=1; i<=n; ++i)
    {
        scanf("%d",&x);
        add(i,T,x),add(T,i,0);ans+=x;
    }
    for(int i=1;i<=m;++i) scanf("%d",vt+i);
    for(int i=1;i<=m;++i) add(S,n+i,vt[i]),add(n+i,S,0);
    for(int i=1;i<=m;++i) {
    	for(scanf("%d",&y);y--;){
    		scanf("%d",&x);
    		add(n+i,x,vt[i]);
    		add(x,n+i,0);
		}
	}
    while(bfs()) ans-=dfs(S,INF);
    printf("%d\n",ans);
    }
}

C++(clang++11) 解法, 执行用时: 12ms, 内存消耗: 2808K, 提交时间: 2021-04-14 16:05:28

#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
using namespace std;
#define For(i,l,r) for(int i=l;i<=r;i++)
#define FOR(i,u) for(int i=now[u];i;i=nxt[i])
#define INF 0x3fffffff
#define MAXN 1501
#define MAXM 1000001
int T,N,M,s,t,fst[MAXN],now[MAXN],cnt=1,to[MAXM],flow[MAXM],nxt[MAXM],dep[MAXN];
int get(){int x=0;char c=getchar();while(c<'0'||c>'9')c=getchar();while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();return x;}
void add(int u,int v,int f){to[++cnt]=v,flow[cnt]=f,nxt[cnt]=fst[u],fst[u]=cnt;to[++cnt]=u,flow[cnt]=0,nxt[cnt]=fst[v],fst[v]=cnt;}
bool bfs()
{
	memset(dep,-1,sizeof(dep));dep[s]=0;queue<int>q;q.push(s);
	while(!q.empty()){int u=q.front();q.pop();if(u==t)return 1;now[u]=fst[u];FOR(i,u)if(flow[i]&&dep[to[i]]==-1)dep[to[i]]=dep[u]+1,q.push(to[i]);}return 0;
}
int dfs(int u,int in)
{
	if(u==t||!in)return in;int ans=0;
	FOR(i,u){now[u]=i;if(dep[to[i]]!=dep[u]+1)continue;int tmp=dfs(to[i],min(in,flow[i]));in-=tmp,ans+=tmp,flow[i]-=tmp,flow[i^1]+=tmp;if(!in)break;}return ans;
}
int main()
{
	cin>>T;
	while(T--)
	{
		cin>>N>>M;s=0,t=N+M+1;memset(fst,0,sizeof(fst));cnt=1;int ans=0;For(i,1,N){int x=get();ans+=x;add(s,i,x);}For(i,1,M)add(i+N,t,get());
		For(i,1,M){int K=get();while(K--)add(get(),i+N,10000);}while(bfs())ans-=dfs(s,INF);cout<<ans<<endl;
	}
	return 0;
}

详情