这题的网络是这样建的。设一个源点s，s将于客户节点相连，连接方式为对考虑一个猪圈是第一次被光顾s将于这位顾客之间
有一条流容量是该猪圈的猪数，若这个猪圈被人光顾过，则在这个顾客和前一个顾客间有一条无限流量的通道。依次下去完成顾客
节点和s，顾客节点和顾客阶段间的网络。最后是顾客和汇点的网络，每个顾客和汇点t都有条通道，容量是顾客希望购买的数量。
- /*pku1149
- Name: PIGS
- Date: 27-07-08 16:42
- Description: 最大流
- */
- #include<stdio.h>
- #include<algorithm>
- #define pr printf
- #define MAX 10000000
- int pig[1002][103];
- int a[103][103],max;//容量
- int b[103][103];
- int m,n,min;
- #define SIZE 1000
- #define MAXN 103
- #define inf 1000000000
- int max_flow(int n,int mat[][MAXN],int source,int sink,int flow[][MAXN]){
- int pre[MAXN],que[MAXN],d[MAXN],p,q,t,i,j;
- if (source==sink) return inf;
- for (i=0;i<n;i++)
- for (j=0;j<n;flow[i][j++]=0);
- for (;;){
- for (i=0;i<n;pre[i++]=0);
- pre[t=source]=source+1,d[t]=inf;
- for (p=q=0;p<=q&&!pre[sink];t=que[p++])
- for (i=0;i<n;i++)
- if (!pre[i]&& (j=mat[t][i]-flow[t][i]))
- pre[que[q++]=i]=t+1,d[i]=d[t]<j?d[t]:j;
- else if (!pre[i]&& (j=flow[i][t]))
- pre[que[q++]=i]=-t-1,d[i]=d[t]<j?d[t]:j;
- if (!pre[sink]) break;
- for (i=sink;i!=source;)
- if (pre[i]>0)
- flow[pre[i]-1][i]+=d[sink],i=pre[i]-1;
- else
- flow[i][-pre[i]-1]-=d[sink],i=-pre[i]-1;
- }
- for (j=i=0;i<n;j+=flow[source][i++]);
- return j;
- }
- int main(){
- int i,j,A,B,key;
- scanf("%d%d",&m,&n);
- memset(a,inf,sizeof(a));//0表示没有流量
- for(i=1;i<=m;i++)
- {
- scanf("%d",&pig[i][0]);
- pig[i][102]=0;
- }
- for(i=1;i<=n;i++)
- {
- scanf("%d",&A);
- for(j=1;j<=A;j++)
- {
- scanf("%d",&key);
- if(pig[key][102]==0){a[0][i]+=pig[key][0];}//猪圈只和第一个顾客相连
- for(int k=pig[key][102];k>=1;k--){
- a[pig[key][k]][i]=MAX;
- }
- pig[key][++pig[key][102]]=i;
- }
- scanf("%d",&B);
- a[i][n+1]=B;
- }
- max=max_flow(n+2,a,0,n+1,b);//0是源点，n+1是汇点
- pr("%d/n",max);
- }