题目描述 Description

XX酒店的老板想成为酒店之王，本着这种希望，第一步要将酒店变得人性化。由于很多来住店的旅客有自己喜好的房间色调、阳光等，也有自己所爱的菜，但是该酒店只有p间房间，一天只有固定的q道不同的菜。

有一天来了n个客人，每个客人说出了自己喜欢哪些房间，喜欢哪道菜。但是很不幸，可能做不到让所有顾客满意（满意的条件是住进喜欢的房间，吃到喜欢的菜）。

这里要怎么分配，能使最多顾客满意呢？

 输入输出格式 Input/output

输入格式：

第一行给出三个正整数表示n,p,q(<=100)。

之后n行，每行p个数包含0或1，第i个数表示喜不喜欢第i个房间（1表示喜欢，0表示不喜欢）。

之后n行，每行q个数，表示喜不喜欢第i道菜。

输出格式：

最大的顾客满意数。

 输入输出样例 Sample input/output

样例测试点#1

输入样例：

2 2 2

1 0

1 0

1 1

1 1

输出样例：

1

 

分析：

构造一个图，模拟出源点S和汇点T，把每个人拆成两部分，按照S->房间->人->人->饭->T的顺序构建图，跑一遍最大流。可完美解决。

 

Dinic：

#include
        
           #include
         
            #include
          
             #include
           
              using namespace std;  int n,p,q,s,t,m,ans,a[1000][1000],room[201][201],dish[201][201],dis[1000],sq[1000];  bool BFS()  {       memset(dis,0xff,sizeof(dis));       dis[1]=0;       int x,head=0,tail=1;       sq[1]=1;       while (head
            
             0&&dis[i]<0)                 {                                       dis[i]=dis[x]+1;                                       tail++;                                       sq[tail]=i;                 }       }       if (dis[t]>0) return true; else return false;  }  int find(int x,int low)  {      int delta=0;      if (x==t) return low;      for (int i=1;i<=t;i++)          if (dis[i]==dis[x]+1&&a[x][i]>0&&(delta=find(i,min(low,a[x][i]))))          {                                           a[x][i]-=delta;                                           a[i][x]+=delta;                                           return delta;          }      return 0;  }   int main()  {      memset(room,0,sizeof(room));      memset(dish,0,sizeof(dish));      memset(a,0,sizeof(a));      scanf("%d%d%d",&n,&p,&q);      for (int i=1;i<=n;i++)          for (int j=1;j<=p;j++)              scanf("%d",&room[i][j]);      for (int i=1;i<=n;i++)          for (int j=1;j<=q;j++)              scanf("%d",&dish[i][j]);      s=1;      t=n+n+p+q+2;      for (int i=1;i<=p;i++) a[1][i+1]=1;      for (int i=1;i<=n;i++) a[p+1+i][p+n+1+i]=1;      for (int i=1;i<=n;i++)          for (int j=1;j<=p;j++)              if (room[i][j]==1) a[j+1][p+1+i]=1;      for (int i=1;i<=n;i++)          for (int j=1;j<=q;j++)              if (dish[i][j]==1) a[p+n+1+i][p+n+n+1+j]=1;      for (int i=n+n+p+2;i
            
           
          
         
        

耗时：91ms

内存：6381kb

同校大神写的SAP:

#include
        
           #include
         
            #include
          
             #include
           
              using namespace std;  int edge[420][420],dis[420],start[420],gap[420],pre[420];  int main()  {      int a,b,p,q,c,i,j,k,n,m,h,ll,flow;      memset(edge,0,sizeof(edge));      memset(gap,0,sizeof(gap));      memset(start,0,sizeof(start));      cin >> n >> p>> q;  c=p+n; b=c+n;      for ( i=1; i<=n; i++)   for ( j=1; j<=p; j++)      {          cin >> a;          if ( a ) edge[j][i+p]++;      }      for ( i=1; i<=n; i++) edge[i+p][i+c]++;      for ( i=1; i<=n; i++)   for ( j=1; j<=q; j++)      {          cin >> a;          if ( a ) edge[i+c][b+j]++;      }      n=b+q+1;  gap[0]=n+1;      for ( i=1; i<=p; i++) edge[0][i]++;      for ( i=b+1; i
           
          
         
        

耗时：137ms

内存：2805kb

 

就本题来看，构图差不多的情况下，dinic的时效较高，但内存多，spfa时效略逊色，但内存少。

合理构图是关键！