学步园

#include <cstdio>        //EK()算法。时间复杂度（VE^2）
#include <queue>
#include <cstring>
using namespace std;

const int maxn = 1200;
const int INF = (1<<30)-1;
int g[maxn][maxn];
int flow[maxn],pre[maxn];
int rank[maxn][2],pig[maxn];
bool vis[maxn];
int n,m;

int bfs(int s,int e)
{
    memset(pre,-1,sizeof(pre));
    memset(vis,false,sizeof(vis));
    queue<int> q;
    vis[s] = true;
    for(int i=1; i<=n; i++)   flow[i]=INF;
    q.push(s);
    while(!q.empty())
    {
        int now = q.front();
        q.pop();
        if(now==n)  break;
        for(int i=1; i<=n; i++)               //寻找增广路最小流量
        {
            if(!vis[i] && g[now][i]>0)
            {
                vis[i] = true;
                flow[i] = min(flow[now],g[now][i]);
                pre[i] = now;
                q.push(i);
            }
        }
    }
    if(!vis[e] || e==1)                         //找不到完整的增广路or源点汇点重合
        return -1;
    else
        return flow[e];
}

int EK(int s,int e)
{
    int temp,d,res,maxflow;
    maxflow = 0;
    while((d=bfs(s,e))!=-1)
    {
        maxflow += d;
        temp=n;
        while(temp!=1)
        {
            res = pre[temp];
            g[res][temp]-=d;               //正向边
            g[temp][res]+=d;               //反向边
            temp = res;
        }
    }
    return maxflow;
}

int main()
{
	// freopen("in","r",stdin);
	// freopen("out","w",stdout);

    int start,end,capacity,a,tmp,i,j;
    
    while(scanf("%d %d",&m,&n)!=EOF)
    {
        memset(g,0,sizeof(g));
        memset(rank,0,sizeof(rank));

        for(i=1;i<=m;i++)
        	scanf("%d",&pig[i]);
        for(i=1;i<=n;i++)
        {
        	scanf("%d",&a);
        	for(j=0;j<a;j++)
        	{
        		scanf("%d",&tmp);
        		rank[tmp][0]++;
        		if(rank[tmp][0]==1){
        			g[1][i+1]+=pig[tmp];
        			rank[tmp][1]=i;
        		}
        		else if(rank[tmp][0]==2) 
        			g[rank[tmp][1]+1][i+1]=INF;
        	}
        	scanf("%d",&a);
        	g[i+1][n+2]=a;
        }
        n+=2;
        printf("%d\n",EK(1,n));
    }
    return 0;
}