POJ3281 Dining(拆点构图 + 最大流）

题意：有F种食物,D种饮料N头奶牛,只能吃某种食物和饮料(而且只能吃特定的一份)

一种食物被一头牛吃了之后,其余牛就不能吃了
第一行有N,F,D三个整数
接着2-N+1行代表第i头牛,前面两个整数是Fi与Di(食物与饮料的种类数量),接着是食物的种类与饮料的种类
要求输出最多分配能够满足的牛的数量

分析：本想最大匹配搞，然后发现牛不仅要匹配食物还要匹配饮料。

最大流拆点构图，食物 - 牛- 饮料，但是由于一个牛只能选择一个食物和一个饮料，也就是说牛这个节点有限制，最大就是1，然后把牛这个节点拆成牛 - 牛其中之间流量是1，

于是最后模型就是食物 - 牛 - 牛 - 饮料节点之间的流量都是1.

 #include <iostream>

 #include <cstdio>

 #include <algorithm>

 #include <queue>

 #include <cstring>

 using namespace std;

 const int Max = ;

 const int INF = 0x3f3f3f3f;

 int g[Max][Max];

 int N, F, D;

 int pre[Max];

 int BFS()

 {

     memset(pre, -, sizeof(pre));

     int MinFlow = INF;

     queue<int> que;

     pre[] = ;

     que.push();

     int des = F +  * N + D + ;

     while (!que.empty())

     {

         int x = que.front();

         que.pop();

         if (x == des)

             break;

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

         {

             if (pre[i] == - && g[x][i])

             {

                 if (MinFlow > g[x][i])

                 {

                     MinFlow = g[x][i];

                 }

                 pre[i] = x;

                 que.push(i);

             }

         }

     }

     if (pre[des] == -)

         return -;

     return MinFlow;

 }

 void EK()

 {

     int MaxFlow = , inFlow = , des;

     while ( (inFlow = BFS()) != -)

     {

         MaxFlow += inFlow;

         des = F +  * N + D + ;

         while (des != )

         {

             g[des][pre[des]] += inFlow;

             g[pre[des]][des] -= inFlow;

             des = pre[des];

         }

     }

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

 }

 void buildGraph()

 {

     while (scanf("%d%d%d", &N, &F, &D) != EOF)

     {

         memset(g, , sizeof(g));

         int fd, fnum, dnum;

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

         {

             scanf("%d%d", &fnum, &dnum);

             for (int j = ; j < fnum; j++)

             {

                 scanf("%d", &fd);

                 g[][fd] = ;  // 0点作为起点连接每个食物

                 g[fd][F + i] = ; // 食物和牛相连，食物最大F，

             }

             g[F + i][F + N + i] = ; // 牛 和 牛相连

             for (int j = ; j <= dnum; j++)

             {

                 scanf("%d", &fd);

                 g[F + N + i][F + N + N + fd] = ;  // 牛和饮料相连

                 g[F + N + N + fd][F + N + N + D + ] = ; // 设一个终点让每一个 饮料 和他相连，流量为1

             }

         }

         EK();

     }

 }

 int main()

 {

     buildGraph();

     return ;

 }

巴特西

POJ3281 Dining(拆点构图 + 最大流）

最新文章

热门文章