hdu4292Food（最大流Dinic算法）

时间：2021-11-28 03:32:49
  /*
  　　  题意：每一个人都有喜欢的吃的和喝的，每一个人只选择一个数量的吃的和一个数量的喝的，问能满足最多的人数！？
　　　　思路：建图很是重要！f-food, p-people, d-drink
　　　　建图：  0（源点）--->f--->p---->p'---->d--->t(汇点)
　　　         将人拆分很是重要，因为每一个人最多只能有一种选择，也就是p--->p'的最大流量是 1！
　　　　　　　　如果还是不清楚，看一看下图的例子，将人拆分与不拆分的区别！
　　　　　　　                 　hdu4292Food（最大流Dinic算法）
  */
  1 #include<iostream>

 #include<cstring>

 #include<cstdio>

 #include<algorithm>

 #include<vector>

 #include<queue>

 #define N 850

 #define M 201000

 #define INF 0x3f3f3f3f

 using namespace std;

 struct EDGE{

     int v, cap, nt;

 };

 int first[N];

 EDGE g[M];

 int cnt;

 int n, f, d;

 void addEdge(int u, int v, int cap){

     g[cnt].v=v;

     g[cnt].cap=cap;

     g[cnt].nt=first[u];

     first[u]=cnt++;

     g[cnt].v=u;

     g[cnt].cap=;

     g[cnt].nt=first[v];

     first[v]=cnt++;

 }

 int ans, ss;

 queue<int>q;

 int dist[N];

 bool bfs(){

     memset(dist, , sizeof(dist));

     dist[]=;

     q.push();

     while(!q.empty()){

           int u=q.front();

         q.pop();

         for(int e=first[u]; ~e; e=g[e].nt){

                int v=g[e].v;

             int cap=g[e].cap;

             if(!dist[v] && cap>){

                 dist[v]=dist[u]+;

                 q.push(v);

             }

         }

     }

     if(dist[ss+]==) return false;

     return true;

 }

 int dfs(int u, int flow){

     int ff;

     if(u==ss+) return flow;

     for(int e=first[u]; ~e; e=g[e].nt){

         int v=g[e].v;

         int cap=g[e].cap;

         if(dist[v]==dist[u]+ && cap> && (ff=dfs(v, min(cap, flow)))){

             g[e].cap-=ff;

             g[e^].cap+=ff;

             return ff;

         }

      }

     dist[u]=-;//表示u节点不能到达汇点！

     return ;

 }

 void Dinic(){

     ans=;

     int d;

     while(bfs())

          while(d=dfs(, INF))

             ans+=d;

 }

 int main(){

     while(scanf("%d%d%d", &n, &f, &d)!=EOF){

         ss=*n+f+d;

         cnt=;

         memset(first, -, sizeof(first));

         for(int i=; i<=f; ++i){//源点到吃的建一条有向边，最大流量为吃的的数量

             int x;

             scanf("%d", &x);

             addEdge(, i, x);

         }

         for(int i=; i<=d; ++i){//喝的到汇点建一条有向边，最大流量为喝的的数量

             int x;

             scanf("%d", &x);

             addEdge(n*+f+i, ss+, x);

         }

         for(int i=; i<=n; ++i){//吃的到人建一条有向边，最大流量为1

             getchar();

             for(int j=; j<=f; ++j){

                 char ch;

                 scanf("%c", &ch);

                 if(ch=='Y')

                     addEdge(j, f+i, );

             }

         }

         for(int i=; i<=n; ++i){//人到喝的建一条有向边，最大流量为1

             addEdge(f+i, n+f+i, );//人属于节点容量，将人进行拆分，因为每一个人只能有一种选择！

             getchar();

             for(int j=; j<=d; ++j){

                 char ch;

                 scanf("%c", &ch);

                 if(ch=='Y')

                     addEdge(n+f+i, f+n*+j, );

             }

         }

         Dinic();

         printf("%d\n", ans);

     }

     return ;

 }

相关文章