本题的关键在于构造容量网络,看题解之前真的很难想到能用最大流来写这题,看了题解后发现还是很好理解的,构图思维有待培养;
构图方案如下:
1.将顾客看做结点,并另设汇点和源点。
2.源点和每个猪圈第一个访问的顾客相关联,边的权是猪圈里猪的初始值,重边直接合并。
3.顾客j紧跟着i之后则边<i,j>的权赋为Inf,因为这里猪的数量可以任意调整
#include <cstdio>
#include <string.h>
#define min(a,b) ((a)>(b))?(b):(a)
using namespace std ;
const int maxn=105;
const int maxm=1005;
const int Inf=0x7fffffff;
int pig[maxm];
int cap[maxn][maxn],flow[maxn][maxn];//source is 0 ,sink is n+1;
int p[maxn],minflow[maxn],queue[maxn+10];
int k_vis[maxm];
int m,n;
int maxflow (int s,int t)
{
int f=0;
int u,v,rear,head;
memset (queue , 0 , sizeof(queue));
memset (flow , 0 , sizeof(flow));
while (true)
{
memset (minflow , 0 , sizeof(minflow));
minflow[s]=Inf;
head=0;
rear=1;
queue[head]=s;
while (head<rear)
{
u=queue[head]; head++;
for (v=0 ; v<=t ; ++v)
{
if(!minflow[v] && cap[u][v]>flow[u][v])
{
p[v]=u;
queue[rear]=v;rear++;
minflow[v]=min(minflow[u],cap[u][v]-flow[u][v]);
}
}
}
if(!minflow[t])break;
for (u=t ; u!=s ; u=p[u])
{
flow[u][p[u]]-=minflow[t];
flow[p[u]][u]+=minflow[t];
}
f+=minflow[t];
}
return f;
}
int main ()
{
int i,a,b,j,key;
while (scanf("%d%d",&m,&n)!=EOF)
{
memset (k_vis , 0 , sizeof(k_vis));
memset (cap , 0 , sizeof(cap));
for (i=0 ; i<m ; ++i)
scanf("%d",pig+i);
for (i=1 ; i<=n ; ++i)
{
scanf("%d",&a);
for (j=0 ; j<a ; ++j)
{
scanf("%d",&key);
if(!k_vis[key])
cap[0][i]+=pig[key-1];
else cap[k_vis[key]][i]=Inf;
k_vis[key]=i;//record the last one has visited the pigs house
}
scanf("%d",&b);
cap[i][n+1]+=b;
}
printf("%d\n",maxflow(0,n+1));
}
return 0;
}