题目描述 Description

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

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

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

输入输出格式 Input/output

输入格式：

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

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

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

输出格式：

最大的顾客满意数。

输入样例：

2 2 2

1 0

1 0

1 1

1 1

输出样例：

1

题解：裸的网络流。别忘了把一个人拆成两个人。

#include
     
        #include
      
         using namespace std;    const int INF=~0U>>2;  int s=0,t;  int n,p,q;  int map[405][405];  int dis[405],sumd[405],now[405];  int fanhui[405],pre[405];  int ans=0;    void init()  {      scanf("%d%d%d",&n,&p,&q);      t=2*n+p+q+1;      for (int i=1; i<=p; i++) map[0][i]=1;        for (int i=1; i<=n; i++) map[i+p][i+p+n]=1;        for (int i=1; i<=q; i++) map[i+p+n+n][t]=1;        for (int i=1; i<=n; i++)        for (int j=1; j<=p; j++) cin >> map[j][i+p];        for (int i=1; i<=n; i++)        for(int j=1; j<=q; j++) cin >> map[i+p+n][j+p+n+n];    }    void sap()  {      sumd[0]=t+1;//sumd[i]表示编号为i的点的数量     int i=s;      now[i]=0;//now[i]表示i连接的点     int flow=INF;      while (dis[s]
       
        0 && dis[i]==dis[j]+1)              {                        flag=true;                   if (map[i][j]
        
         0) kk=dis[j];            sumd[dis[i]]--;            if (sumd[dis[i]]==0) break;//如果标号出现断层也就不可能找到增广路           dis[i]=kk+1;            sumd[dis[i]]++;            flow=fanhui[i];            if (i!=0) i=pre[i];       }       cout << ans;       return;  }    int main()  {      init();      sap();      return 0;  }