hdu 4292(拆点+最大流）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4292

思路：为了控制一个人只连一瓶饮料，一份食物，那么我们可以把一个人拆成两个，他们之间连一条权值为1的边，另外左边连它喜欢的食物，权值为1，右边连它喜欢的饮料，权值为1，在起点连食物的时候加流量限制，终点加流量限制，跑一遍最大流即可。

View Code

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 using namespace std;
  5 #define MAXN 1111
  6 #define MAXM 88888888
  7 struct Edge{
  8     int v,cap,next;
  9 }edge[MAXM];
 10 
 11 int head[MAXN];
 12 int pre[MAXN];
 13 int cur[MAXN];
 14 int level[MAXN];
 15 int gap[MAXN];
 16 int NE,NV,vs,vt,n,f,d;
 17 int Food[MAXN];
 18 int Drink[MAXN];
 19 
 20 
 21 void Insert(int u,int v,int cap,int cc=0){
 22     edge[NE].v=v;edge[NE].cap=cap;
 23     edge[NE].next=head[u];head[u]=NE++;
 24 
 25     edge[NE].v=u;edge[NE].cap=cc;
 26     edge[NE].next=head[v];head[v]=NE++;
 27 }
 28 
 29 
 30 
 31 int SAP(int vs,int vt){
 32     memset(pre,-1,sizeof(pre));
 33     memset(level,0,sizeof(level));
 34     memset(gap,0,sizeof(gap));
 35     for(int i=0;i<NV;i++)cur[i]=head[i];
 36     int u=pre[vs]=vs,maxflow=0,aug=-1;
 37     gap[0]=NV;
 38     while(level[vs]<NV){
 39 loop:
 40         for(int &i=cur[u];i!=-1;i=edge[i].next){
 41             int v=edge[i].v;
 42             if(edge[i].cap&&level[u]==level[v]+1){
 43                 aug==-1?aug=edge[i].cap:aug=min(aug,edge[i].cap);
 44                 pre[v]=u;
 45                 u=v;
 46                 if(v==vt){
 47                     maxflow+=aug;
 48                     for(u=pre[u];v!=vs;v=u,u=pre[u]){
 49                         edge[cur[u]].cap-=aug;
 50                         edge[cur[u]^1].cap+=aug;
 51                     }
 52                     aug=-1;
 53                 }
 54                 goto loop;
 55             }
 56         }
 57         int minlevel=NV;
 58         for(int i=head[u];i!=-1;i=edge[i].next){
 59             int v=edge[i].v;
 60             if(edge[i].cap&&minlevel>level[v]){
 61                 cur[u]=i;
 62                 minlevel=level[v];
 63             }
 64         }
 65         gap[level[u]]--;
 66         if(gap[level[u]]==0)break;
 67         level[u]=minlevel+1;
 68         gap[level[u]]++;
 69         u=pre[u];
 70     }
 71     return maxflow;
 72 }
 73 
 74 int main(){
 75     char str[MAXN];
 76     while(~scanf("%d%d%d",&n,&f,&d)){
 77         vs=0,vt=f+2*n+d+1,NV=vt+1,NE=0;
 78         memset(head,-1,sizeof(head));
 79         for(int i=1;i<=f;i++){
 80             scanf("%d",&Food[i]);
 81             Insert(vs,i,Food[i]);//源点与每一种食物连容量为food[i]的边。
 82         }
 83         for(int i=1;i<=d;i++){
 84             scanf("%d",&Drink[i]);
 85             Insert(i+2*n+f,vt,Drink[i]);//每种饮料与汇点连容量为Drink[i]的边。
 86         }
 87         for(int i=1;i<=n;i++){
 88             Insert(i+f,i+f+n,1);//将人拆点，人与人之间连容量为1的边
 89         }
 90         for(int i=1;i<=n;i++){
 91             scanf("%s",str+1);
 92             for(int j=1;j<=f;j++){
 93                 if(str[j]=='Y'){
 94                     Insert(j,i+f,1);//食物与人连边。
 95                 }
 96             }
 97         }
 98         for(int i=1;i<=n;i++){
 99             scanf("%s",str+1);
100             for(int j=1;j<=d;j++){
101                 if(str[j]=='Y'){
102                     Insert(i+f+n,f+2*n+j,1);//人与饮料之间连容量为1的边
103                 }
104             }
105         }
106         printf("%d\n",SAP(vs,vt));
107     }
108     return 0;
109 }