poj 3281 Dining (最大网络流)

题目链接：

题目大意：

　　有n头牛，f种食物，d种饮料，第i头牛喜欢fi种食物和di种饮料，每种食物或者饮料被一头牛选中后，就不能被其他的牛选了，问最多能满足多少头牛的要求？

解题思路：

　　最大匹配问题，关键在于如何建图，可以虚构出来一个源点，一个汇点，一共需要f+d+2*n+2个点即可，建图为：源点—>食物—>牛—>牛—>饮料—> 汇点。把牛作为点拆开建图是为了让一头牛只对应一种饮料和一种食物，避免出现对应多种饮料或者多种食物的情况。

代码：

 #include <cstdio>

 #include <cstring>

 #include <cstdlib>

 #include <algorithm>

 #include <iostream>

 #include <cmath>

 #include <queue>

 using namespace std;

 #define maxn 0x3f3f3f3f

 #define N 410

 int map[N][N], Layer[N], s, e;

 bool visit[N];

 bool CountLayer();

 int Dinic ();

 int main ()

 {

     int n, f, d, x, y, m;

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

     {

         s = , e = f + d + n + n + ;

         memset (map, , sizeof(map));

         for (int i=; i<=f; i++)

             map[][i] = ;//食物和源点连线

         for (int i=; i<=d; i++)

             map[i+f+*n][e] = ;//饮料和汇点链接

         for (int i=; i<=n; i++)

             map[i+f][i+f+n] = ;//对应的牛和牛链接

         for (int i=; i<=n; i++)

         {//建立牛和食物及饮料的关系

             int num = f + i;

             scanf ("%d %d", &x, &y);

             while (x --)

             {

                 scanf ("%d", &m);

                 map[m][num] = ;

             }

             while (y --)

             {

                 scanf ("%d", &m);

                 map[num + n][m+f+*n] = ;

             }

         }

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

     }

     return ;

 }

 bool CountLayer()

 {

     deque <int> Q;

     memset (Layer, , sizeof(Layer));

     Layer[] = ;

     Q.push_back();

     while (!Q.empty())

     {

         int nd = Q.front();

         Q.pop_front();

         for (int i=s; i<=e; i++)

         {

             if (map[nd][i]> && !Layer[i])

             {

                 Layer[i] = Layer[nd] + ;

                 if (i == e)

                     return true;

                 else

                     Q.push_back(i);

             }

         }

     }

     return false;

 }

 int Dinic ()//Dinic模板

 {

     int maxnflow = , i;

     while (CountLayer())

     {

         deque<int>Q;

         memset (visit, , sizeof(visit));

         visit[] = ;

         Q.push_back();

         while (!Q.empty())

         {

             int nd = Q.back();

             if (nd != e)

             {

                 for (i=; i<=e; i++)

                 {

                     if (map[nd][i]> && Layer[i] == Layer[nd]+ && !visit[i])

                     {

                         visit[i] = ;

                         Q.push_back(i);

                         break;

                     }

                 }

                 if (i > e)

                     Q.pop_back();

             }

             else

             {

                 int minflow = maxn;

                 int mv;

                 for (i=; i<Q.size(); i++)

                 {

                     int ns = Q[i-];

                     int ne = Q[i];

                     if (map[ns][ne] < minflow)

                     {

                         minflow = map[ns][ne];

                         mv = ns;

                     }

                 }

                 maxnflow += minflow;

                 for (i=; i<Q.size(); i++)

                 {

                     int ns = Q[i-];

                     int ne = Q[i];

                     map[ns][ne] -= minflow;

                     map[ne][ns] += minflow;

                 }

                 while (!Q.empty() && Q.back() != mv)

                     Q.pop_back();

             }

         }

     }

     return maxnflow;

 }

巴特西

poj 3281 Dining (最大网络流)

最新文章

热门文章