qus的博客

#include<iostream>
#include<cmath>
#include<string>
using namespace std;
#define inf 1000000000
#define MAXN 105
int mat[MAXN][MAXN],flow[MAXN][MAXN];
int pig[1003][MAXN];
int N,M;
int solve()
{
 int pre[MAXN],que[MAXN],d[MAXN];
 int i,j,t=N+2,s=1;
 for(i=0;i<=N+2;i++)
  for(j=0;j<=N+2;j++)
   flow[i][j]=0;
 while(1)
 {
  memset(pre,0,sizeof(pre));
  int head=0,tail=1;
  pre[s]=s;
  d[s]=inf;
  que[0]=s;
  while(head<tail && pre[t]==0)
  {
   i=que[head];
   for(j=1;j<=N+2;j++)
   {
    if(pre[j]==0)
    {
     if(mat[i][j]>flow[i][j])
     {
      pre[j]=i;
      que[tail]=j;
             d[j]=d[i]<mat[i][j]-flow[i][j]?d[i]:mat[i][j]-flow[i][j];
      tail++;
     }
     else if(flow[j][i]>0)
     {
      pre[j]=-i;
      que[tail]=j;
      d[j]=d[i]<flow[j][i]?d[i]:flow[j][i];
      tail++;
     }
    }
   }
   head++;
  }
  if(pre[t]==0){break;}
  i=t;
  while(i!=s)
  {
   j=abs(pre[i]);
   if(pre[i]>0){flow[j][i]+=d[t];}
   else{flow[i][j]-=d[t];}
   i=j;
  }
 }
 int ans=0;
 for(i=1;i<=N+2;i++)
 {
  ans+=flow[s][i];
 }
 printf("%d\n",ans);
 return 0;
}
int main()
{
 int i,j;
 while(scanf("%d%d",&M,&N)!=EOF)
 {
  for(i=1;i<=M;i++)
  {
   scanf("%d",&pig[i][1]);
   pig[i][103]=1;
  }
  for(i=2;i<=N+1;i++)
  {
   int A;
   scanf("%d",&A);
   for(j=1;j<=A;j++)
   {
    int key;
    scanf("%d",&key);
    if(pig[key][103]==1){mat[1][i]+=pig[key][1];}
    int k;
    for(k=pig[key][103];k>=2;k--){
     mat[pig[key][k]][i]=inf;
    }
    pig[key][++pig[key][103]]=i;
   }
   int B;
   scanf("%d",&B);
   mat[i][N+2]=B;
  }
  solve();
 }
}