P4638 [SHOI2011] 银行家 题解

· · 个人记录

原题传送门

考虑网络流

考虑建图，我们发现，若上面有个人有金库 i 的钥匙，而下面的人也有金库 i 的钥匙，那么我们相当于可以让上面的人拿走所有钱，而下面的人从上面的人的手上拿走钱。

那么建图就可以为：

从源点向每个金库连边，边权为金库金币数量。

对于每个人，他拥有的金库钥匙，若他是第一个拥有该金库钥匙的人，则从金库向该人连边，边权为 \inf，若不是，则从最近拥有该金库钥匙的人向该人连边，边权为 \inf

对于每个人，从该人向汇点连边，边权为他需要的金币数。

跑最大流即可

上代码：

#include<bits/stdc++.h>
using namespace std;
const int N=610,M=2510,INF=1e9+7;
int m,n,s,t,mon,la[M];
int h[M+N],e[M*N*2],w[M*N*2],ne[M*N*2],idx=1;
void add(int a,int b,int c)
{
    e[++idx]=b;
    w[idx]=c;
    ne[idx]=h[a];
    h[a]=idx;

    e[++idx]=a;
    w[idx]=0;
    ne[idx]=h[b];
    h[b]=idx;
}
int dep[M+N];
bool bfs()
{
    for(int i=s;i<=t;i++)
        dep[i]=INF;
    dep[s]=0;
    queue<int> q;
    q.push(s);
    while(!q.empty())
    {
        int now=q.front();
        q.pop();
        for(int i=h[now];i!=-1;i=ne[i])
        {
            int j=e[i];
            if(w[i]&&dep[j]==INF)
            {
                dep[j]=dep[now]+1;
                if(j==t) return true;
                q.push(j);
            }
        }
    }
    return false;
}
int dfs(int wz,int k)
{
    if(wz==t) return k;
    int re=0;
    for(int i=h[wz];k&&i!=-1;i=ne[i])
    {
        int j=e[i];
        if(w[i]&&dep[j]==dep[wz]+1)
        {
            int tzy=dfs(j,min(k,w[i]));
            k-=tzy;
            w[i]-=tzy;
            w[i^1]+=tzy;
            re+=tzy;
        }
    }
    return re;
}
int main()
{
    memset(h,-1,sizeof h);
    scanf("%d %d",&m,&n);
    s=0,t=m+n+1;
    for(int i=1;i<=m;i++)
    {
        scanf("%d",&mon);
        add(s,i,mon);
        la[i]=i;
    }
    int k,p,c;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&k);
        for(int j=1;j<=k;j++)
        {
            scanf("%d",&p);
            add(la[p],i+m,INF);
            la[p]=i+m;
        }
        scanf("%d",&c);
        add(i+m,t,c);
    }
    int ans=0;
    while(bfs()) ans+=dfs(s,INF);
    printf("%d\n",ans);
    return 0;
}